What's the Entropy of a Random Integer?
quomodocumque.wordpress.com
quomodocumque.wordpress.com
That's not what the (clumsily written) article is about. It's not about sampling the integers to choose an integer, it's about sampling the prime factors of an integer, as a measure of evenness of distribution of prime factors.
It's measuring the information in the prime factorization, the information in the number as a value.
like, the part where they get a_i log p_i , well, the sum of this over i is gives the number, but it seemed like they were treating this as… a_i being a random variable associated to p_i , or something? I wasn’t really clear on what they were doing with that.
Take an $n$, chosen from $[N,2N]$. Take it's prime factorization $n = \prod_{j=1}^{k} q_j^{a_j}$. Take the logarithm $\log(n) = \sum_{j=1}^{k} a_j \log(q_j)$.
Divide by $\log(n)$ to get the sum equal to $1$ and then define a weight term $w _ j = a_j \log(q_j)/\log(n)$.
Think of $w_j$ as "probabilities". We can define an entropy of sorts as $H_{factor}(n) = - \sum_j w_j \log(w_j)$.
The mean entropy is, apparently:
$$ E_{n \in [N,2N]}[ H_{factor}(n) ] = E_{n\in[N,2N] [ - \sum_j w_j(n) \log(w_j(n)) ] $$
Heuristics (such as Poisson-Dirichlet) suggest this converges to 1 as $N \to \infty$.
OpenAI tells me that the reason this might be interesting is that it's giving information on whether a typical integer is built from one, or a few, dominant prime(s) or many smaller ones. A mean entropy of 1 is saying (apparently) that there is a dominant prime factor but not an overwhelming one. (I guess) a mean to 0 means dominant prime, mean to infinity means many small factors (?) and oscillations mean no stable structure.
Unfortunately we weren't reviewing his work, just trusting his reports, as we were overworked getting our own parts done. After a three months of this I said to the project lead: something smells wrong, because he hasn't filed a single bug against my design yet.
So we looked at his code, lots of files and lots of code written, all of it plumbing and test case generation, but he hadn't built the model of the chip's behavior. At the heart of it was a function which was something like:
bool verify_pins(...) {
return true;
}
My boss and I literally slept at work for a month, with my boss building the model and fixing other TB bugs, and I addressed the RTL bugs in the DUT as he found them.
The entropy of a random integer N is the volume of the gap between how much space N takes up and how much space its internal components take up.
This can be visualized as The City of N, in base 2. (OP used log_e, but that's too hard to draw.)
1. The Foundation (The Factors)
Take a random number N and break it into its prime factors. We write these prime factors in binary, side-by-side, along the bottom of a page.
The total width of this baseline is roughly log_2(N)(the number of bits in N).
2. The Cloud Ceiling (The Potential)
We write down the length of (N written down in base 2) in base 2. (If N = 46 = 101110 (base 2), its length is ~6 = 110 (base 2),
We write that number vertically (110) to set the Maximum Ceiling Height.
Finally, we look at the number N itself.
3. The Buildings (The Structure):
Above each prime factor, we construct a building.
* The Width: The width of the building is simply the length of that prime factor in bits.
* The Height: To determine how tall the building is, we look at its width and write that number down vertically in binary.
To normalize, we zoom our camera so the length (log) of N fills the view.
The Entropy (The Visible Sky):
The Sky: This is the empty space between the tops of the buildings and the top of the picture (cloud ceiling).
The Entropy of N is exactly the total area of the visible sky.
If N is prime, the building is as wide and tall as the whole city and touches the cloud ceiling. No Sky. Zero Entropy.
If N is a random integer, it usually has one wide building (the largest prime) that is almost as tall as the ceiling, and a few tiny huts (small primes) that leave a massive gap of blue sky above them.
Here is the visualization for N = 46. (Binary 101110, length ~6).
(46)
1 0 1 1 1 0 (length ~5.5)
---------------------------
|1 1 1 1 1|
|0 0 0 0 0|
|1 1|1 1 1 1 1|
+---+---------+
|1 0|1 0 1 1 1|
(2) (23)
Interpretation:
Building 23 is tall. It reaches Level 3 (101 is length 5). It touches the ceiling (Level 3). There is zero sky above it.
Building 2 is short. It only reaches Level 2 (10 is length 2). There is one unit of sky visible above it.
Total Entropy: The total empty area above the buildings is small (just that gap above factor 2), which matches the math: 46 is "low entropy" because it is dominated by the large factor 23.
A number with High Entropy would look like a row of low, equal-height huts, leaving a massive amount of open sky above the entire city.
> It’s easy to wax poetic about entropy, but what is it? I claim it’s the amount of information we don’t know about a situation, which in principle we could learn.
The entropy of a random integer being 1 makes intrinsic sense to me, given I didn't spend years in theoretical math classes