Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If there is a fixed bound $b$ on the number of symbols, can't do better than logarithmic. Not enough strings available. –  André Nicolas Mar 13 '12 at 13:56
    
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). –  dtldarek Mar 13 '12 at 14:31

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
    
Okay, but what if something besides symbols is used? I have no idea what though. Maybe something relating to quantum mechanics? –  Kendall Frey Mar 13 '12 at 14:03
    
The Holevo bound shows that you can't hold more than n bits in n qubits, so quantum mechanics is out. –  Charles Mar 13 '12 at 14:18
    
@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. –  André Nicolas Mar 13 '12 at 14:26
    
@Andre: That requires O(n) space, since you have to store the line as well as the point. –  Kendall Frey Mar 13 '12 at 14:31
1  
@TannerL.Swett: I can store all n bits in /dev/null if I'm not required to retrieve them. –  Charles Mar 13 '12 at 19:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.