1
$\begingroup$

The most intuitive method of representing an integer is in unary. For example, 10 can be represented as 0000000000, ----------, etc. This requires O(n) space.

The most common method is slightly more complicated. Several different symbols can be used. For example 100 can be represented as 1100100, 144, 64, 100, etc. This requires O(log n)

My question is, is there a next step to this 'sequence' that would allow us to store an integer in sub-log space? Any physically possible way counts, even if it isn't feasible.

Any proof or disproof would be appreciated, as long as it isn't too complicated.

  • 0
    If there is a fixed bound $b$ on the number of symbols, can't do better than logarithmic. Not enough strings available.2012-03-13
  • 0
    It would be possible if you would have an infinite alphabet (if you don't have that, can't do better than logarithmic, as pointed out by Andre Nicolas). Is this physically possible? I don't know, but one simple attempt might be using space and positioning (however, maybe there are only finitely many distances between any two things in our universe).2012-03-13

1 Answers 1

1

No, it's not possible, as a simple argument from information theory shows.

Imagine that you want to represent an integer from 0 to 1023 by a sequence of two symbols, 0 and 1. I assert that one sequence must have length at least 10. Why?

Assume the contrary, that each sequence has length $\le 9$. But there are only $2^9 = 512$ unique sequences with at most nine digits. Clearly, you need at least as many sequences as numbers you want to represent.

This argument readily shows that you $Θ(log n)$ symbols to represent a number from $1$ to $n$.

  • 0
    Okay, but what if something besides symbols is used? I have no idea what though. Maybe something relating to quantum mechanics?2012-03-13
  • 0
    The Holevo bound shows that you can't hold more than n bits in n qubits, so quantum mechanics is out.2012-03-13
  • 0
    @KendallFrey: I know almost nothing about quantum mechanics, so assume classical physics. Then the position of a point on a line "stores" any real number with $1$ "symbol." Back in the bad old days, engineers and physicists actually used analog computers to do real computations, so this model of computing is not all that farfetched.2012-03-13
  • 0
    @Andre: That requires O(n) space, since you have to store the line as well as the point.2012-03-13
  • 0
    @Charles Well, you can *store* more than $n$ bits in $n$ qubits; there simply isn't any way of *retrieving* them.2012-03-13
  • 1
    @TannerL.Swett: I can store all n bits in `/dev/null` if I'm not required to retrieve them.2012-03-13