Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and comparision operations are computable in linear time:
Does there exist a representation of integers so that addition, multiplication, and comparison are all doable in linear time? Basically, is there a linear time discretely ordered ring?
(1) How close can we come to linear time multiplication and addition, without compares? Here I assume that the problem sizes may vary, so that we may need a data structure/algorithm that allows for changing integer sizes.
(2) For the complete problem, we can assume that we will find an optimum scheme for multiply, add, and compare on the integers. How close can we get the slowest of these three operations (in the worst case) towards linear time? And on that note, how fast would the other operations be?
FORMAL PROBLEM STATEMENT
As Emil Jeřábek mentions, we'd like to rule out trivial cases and concentrate on worst case behavior for this question.
So we ask, for non-negative integers $\forall x$ and $\forall y$ where $0 \le x < n$ and $0 \le y < n$, can we find a data structure/algorithm that can perform addition, multiplication, and compares with\between $x$ and $y$ in $O(n \log{(n)})$ time and $O(\log^2{(n)})$ space?