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.

not exactly sure how to best ask this. base-$n$ notation involves a series of digits written where each digit is a natural number less than $n$.

is there some math/theory generalization of base-$n$ notation & related operations where $n$ is fractional?

am particularly interested in the case where $1 \leq n \leq 2$. yes of course am familiar with logarithms & exponentiation but this question is a little more "systematic".

a little further background (which is not intended to be definitive or bias any answers too much). the immediate desired application is the study of complexity theory bit vectors. suppose one wants to study operations on bit vectors empirically (ie with computer experiments/simulations).

for the case base $n=2$ there are $n^x=2^x$ possible bit vectors of length $x$. this can grow (in memory & processing requirements) very quickly esp for relatively simple scenarios/constraints eg $x=m^2$ where $m$ is natural. it would be very useful to convert or "scale down" the problem to some possibly more continuous version such that one could study $1 \leq n \leq 2$ and the results would carry/generalize to higher natural $n$. has anyone seen something like this in books or papers?

it appears maybe to be related to something like "fractional bits" that carry "less than 2 states" whatever those might be.

an roughly close example of a strategy along these lines is the "magnification lemma" for studying circuit complexity found the book, Boolean Function Complexity by Stasys Jukna.

share|improve this question
    
What would the digits be in say base 3/2 ? –  coffeemath Jan 25 '13 at 23:06
    
@coffeemath One possibility would be $0$ and $1$, together with constraints against the $1$s clustering too closely (e.g. exclude substrings $11, 1011, \ldots$). This would be analogous to Fibonacci coding, although I imagine the constraints would not be nice unless $n$ is an algebraic integer. –  Erick Wong Jan 25 '13 at 23:13
    
footnote/musing out loud... maybe hamming codes are related? also, hypergraphs are sometimes referred to as "fractional graphs" etc... maybe a fractional graph of the hypercube graph? –  vzn Jan 25 '13 at 23:57

1 Answer 1

Think of a number drawn from the uniform probability distribution on the interval $[0,1)$. For each base-$n$ digit that I fix, the entropy of the remaining distribution decreases by $\log_{2} n$ bits; that is, each base-$n$ digit carries $\log_{2} n$ bits of information about the number. To extrapolate this to $1<n\le 2$, you want to define a sequence of pieces of data (let's still call them digits) that carry less than a single bit of information each.

There are two ways to do this that I can think of. One is to allow multiple representations for a single number. For instance, if the first digit is $A$, then the number is in $[0,2/3)$, and if the first digit is $B$, the number is in $[1/3,1)$; then recursively subdivide these intervals to get the possibilities for the next digit, and so on. Each digit carries an equal amount of information, which is less than one bit. The other way to do it is to have a unique representation for each number, but let one of the two digits be more likely. In this case, the first digit being $B$ means that the number is in $[2/3,1)$. When you see a $B$ (one-third of the time), you've gained $\log_2{3}$ bits; when you see an $A$ (two-thirds of the time), you've gained $\log_2{3/2}=\log_2{3}-1$ bits; so on average each digit carries $\log_2{3} - 2/3$ bits of information, which is again less than one bit.

share|improve this answer

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.