Fibonacci numbers and time-space tradeoffs

Posted on 8 February 2026 by John

A few days ago I wrote about Fibonacci numbers and certificates. As I pointed out in the article, there’s no need to certify Fibonacci numbers, but the point of the post was to illustrate the idea of a solution certificate in a simple context. Practical uses of certificates are more complicated.

This time I want to use Fibonacci numbers to illustrate space tradeoffs. The post on Fibonacci certificates imagined providing someone a pair (F, r) where F is a large Fibonacci number, and r is a certificate proving that F is indeed a Fibonacci number. The goal was to minimize the computational effort to verify F. All the recipient needed to do was compute

| 5F² − r² |.

The number F is a Fibonacci number if and only if this number equals 4. The problem with this scenario is that F and r are both large numbers. They require transmitting and storing a lot of bits.

A much more space-efficient approach would be to transmit the index of the Fibonacci number and have the user compute the number. The example in the certificate post was (12586269025, 28143753123). Since 12586269025 is the 50th Fibonacci number, I could communicate it to someone by simply transmitting the number 50. That saves space, but it puts more computational burden on the recipient.

Fibonacci numbers grow exponentially with index size, and so the size of the nth Fibonacci number in bits is proportional to n. But the number of bits in n is proportional to log n. When n is large, the difference is dramatic.

How many bits are in the 1,000,000th Fibonacci number? The nth Fibonacci number is φⁿ/√5 rounded to the nearest integer, so the number of bits in the millionth Fibonacci number would be

log₂ (φ^1000000/√5) = 1000000 log₂ φ − 0.5 log₂ 5

which is roughly 700,000. By contrast, one million is a 20 bit number. So transmitting “1000000” is far more efficient than transmitting the millionth Fibonacci number.

What does it take to compute the nth Fibonacci number? For small n, it’s fast and easy to compute the Fibonacci numbers up to n sequentially using the definition of the sequence. For large enough n, it would be faster to compute φⁿ/√5. However, the former requires (extended) integer arithmetic, and the latter requires (extended) floating point arithmetic. It’s not clear where the crossover point would be where floating point would be more efficient. That’s the topic of the next post.

Minimum of cosine sum

Posted on 7 February 2026 by John

Suppose f(x) is the sum of terms of the form cos(kx) where k is an integer from a set A with n elements.

$f_A(x) = \sum_{k \in A} \cos(kx)$

Then the maximum value of f is f(0) = n. But what is the minimum value of f?

The Chowla cosine conjecture says that the minimum should be less than −√n for large n. For now the best proven results are much smaller in absolute value [1].

I was playing around with this problem, and the first thing I thought of was to let the set A be the first n primes. This turned out to not be the most interesting example. Since all the primes except for the first are odd, and cos(kπ) = −1 for odd k, the minimum is 2 −n and occurs at π.

Here’s a plot where A is the set of primes less than 100.

For the cosine conjecture to be interesting, the set A should contain a mix of even and odd numbers.

Here’s a plot with A equal to a random selection of 25 points between 1 and 100. (I chose 25 because there are 25 primes less than 100.)

Here’s the Python code I used to generate the two sets A and the function to plot.

import numpy as np
from sympy import prime

def f(x, A):
    return sum([np.cos(k*x) for k in A])

n = 25
A_prime = [prime(i) for i in range(1, n+1)]
np.random.seed(20260207)
A_random = np.random.choice(range(1, 101), size=n, replace=False)

If you wanted to explore the Chowla conjecture numerically, direct use of minimization software is impractical. As you can tell from the plots above, there are a lot of local minima. If the values in A are not too large, you can look at a plot to see approximately where the minimum occurs, then use a numerical method to find the minimum in this region, but that doesn’t scale.

Here’s an approach that would scale better. You could find all the zeros of the derivative of f_A and evaluate the function at each. One of these is the minimum. The derivative is a sum of sines with integer frequencies, and so it could be written as a polynomial in z = exp(ix) [2]. You could find all the zeros of this polynomial using the QR algorithm as discussed in the previous post.

[1] Benjamin Bedert. Polynomial bounds for the Chowla cosine problem. arXiv

[2] You get a polynomial of degree n in z and 1/z. Then multiply by z²ⁿ to get a polynomial in z only of degree 2n.

Eigenvalue homework problems are backward

Posted on 6 February 2026 by John

Classroom

When you take a linear algebra course and get to the chapter on eigenvalues, your homework problems will include a small matrix A and you will be asked to find the eigenvalues. You do this by computing the determinant

det(A − λI) = P(λ)

and getting P(λ), a polynomial in λ. The roots of P are the eigenvalues of A.

Either A will be a 2 × 2 matrix, in which case you can find the roots using the quadratic formula, or the matrix will have been carefully selected so that P(λ) will be easy to factor. Otherwise, finding the roots of a polynomial is hard.

Real world

Numerical algorithms to find eigenvalues have gotten really good. In practice, you don’t compute determinants or find roots of polynomials. Instead you do something like the QR algorithm.

Finding all the roots of a polynomial is a challenging problem, and so what you might do in practice is find the roots by constructing a matrix, called the companion matrix, whose eigenvalues correspond to the roots you’re after.

Summary

As a classroom exercise, you calculate roots of polynomials to find eigenvalues.

In the real world, you might use an eigenvalue solver to find the roots of polynomials.

I wrote a similar post a few years ago. It explains that textbooks definite hyperbolic functions using e^x, but you might want to compute e^x using hyperbolic functions.

Fibonacci number certificates

Posted on 5 February 2026 by John

Suppose I give you a big number F and claim that F is a Fibonacci number. How could you confirm this?

Before I go further, let me say what this post is really about. It’s not about Fibonacci numbers so much as it is about proofs and certificates. There’s no market for large Fibonacci numbers, and certainly no need to quickly verify that a number is a Fibonacci number.

You could write a program to generate Fibonacci numbers, and run it until it either produces F , in which case you know F is a Fibonacci number, or the program produces a larger number than F without having produced F, in which case you know it’s not a Fibonacci number. But there’s a faster way.

A certificate is data that allows you to confirm a solution to a problem in less time, usually far less time, than it took to generate the solution. For example, Pratt certificates give you a way to prove that a number is prime. For a large prime, you could verify its Pratt certificate much faster than directly trying to prove the number is prime.

There is a theorem that says a number f is a Fibonacci number if and only if one of 5f² ± 4 is a perfect square. So in addition to F another number r that is a certificate that F is a Fibonacci number. You compute

N = 5F² − r²

and if N is equal to 4 or −4, you know that F is a Fibonacci number. Otherwise it is not.

Here’s a small example. Suppose I give you (12586269025, 28143753123) and claim that the first number is a Fibonacci number and the second number is its certificate. You can compute

5 × 12586269025² − 28143753123²

and get −4, verifying the claim.

Certificates are all about the amount of computation the verifier needs to do. The prover, i.e. the person producing the certificate, has to do extra work to provide a certificate in addition to a problem solution. This trade-off is acceptable, for example, in a blockchain where a user posts one transaction but many miners will verify many transactions.

Γ(1/n)

Posted on 4 February 2026 by John

If n is a positive integer, then rounding Γ(1/n) up to the nearest integer gives n. In symbols,

$\left\lceil \Gamma\left( \tfrac{1}{n}\right) \right\rceil = n$

We an illustrate this with the following Python code.

>>> from scipy.special import gamma
>>> from math import ceil
>>> for n in range(1, 101):
    ... assert(ceil(gamma(1/n)) == n)

You can find a full proof in [1]. I’ll give a partial proof that may be more informative than the full proof.

The asymptotic expansion of the gamma function near zero is

$\Gamma(z) = \frac{1}{z} - \gamma + {\cal O}(z^2)$

where γ is the Euler-Mascheroni constant.

So when we set z = 1/n we find Γ(1/n) ≈ n − γ + O(1/n²). Since 0 < γ < 1, the theorem above is true for sufficiently large n. And it turns out “sufficiently large” can be replaced with n ≥ 1.

[1] Gamma at reciprocals of integers: 12225. American Mathematical Monthly. October 2022. pp 789–790.

Polish serenity

Posted on 3 February 2026 by John

Yesterday I ran across the following mashup by Amy Swearer of a Polish proverb and the Serenity Prayer.

Lord, grant me the serenity to accept when it’s no longer my circus,
the courage to control the monkeys that are still mine,
and the wisdom to know the difference.

The proverb is “Nie mój cyrk, nie moje małpy,” literally “Not my circus, not my monkeys”.

Satellites have a lot of room

Posted on 2 February 2026 by John

I saw an animation this morning showing how the space above our planet is dangerously crowded with satellites. That motivated me to do a little back-of-the-envelope math.

The vast majority of satellites are in low earth orbit (LEO), which extends from 160 to 2000 km above the earth’s surface. The radius of the earth is about 6400 km, so the volume of the LEO region is

$\frac{4\pi}{3} \left((6400 + 2000)^3 - (6400 + 160)^3\right) \text{km}^3 = 1.3 \times 10^{12} \,\text{km}^3$

There are about 12,500 satellites in LEO, so the average volume of LEO per satellite is about 100,000,000 km³.

Now this isn’t the last word in collision avoidance—there are lots of complications we’re not going to get into here—but it is the first word: there’s a lot of space in space.

Bridging secrets is hard

Posted on 30 January 2026 by John

Cryptocurrency and privacy don’t fit together as easily as you might expect. Blockchains give you the illusion of privacy via pseudonymization: you don’t put your name on a blockchain, but you do put information on a blockchain that can be used to determine your name. Blockchain analysis can often reveal information that no one intended to share.

This is true even for privacy coins like Monero and Zcash. These coins put less information directly on chain in the clear, but they still have to be used with skill to maintain privacy. And because they can offer more privacy, they are harder to use. For example, an exchange might let you swap between a thousand different currencies, but privacy coins are conspicuously missing from the list of options. Or maybe you can move money into Zcash, but not with privacy, i.e. not into the shielded pool.

The Privacy trends for 2026 report from a16z summarizes the current situation very well.

Thanks to bridging protocols, it’s trivial to move from one chain to another as long as everything is public. But, as soon as you make things private, that is no longer true: Bridging tokens is easy, bridging secrets is hard. There is always a risk when moving in or out of a private zone that people who are watching the chain, mempool, or network traffic could figure out who you are. Crossing the boundary between a private chain and a public one—or even between two private chains—leaks all kinds of metadata like transaction timing and size correlations that makes it easier to track someone.

As is often the case, the weak link is the metadata, not the data per se.

Fortunes and Geometric Means

Posted on 24 January 2026 by John

I saw a post on X recently that said

Bill Gates is closer to you in wealth than he is to Elon Musk. Mind blown.

For round numbers, let’s say Elon Musk’s net worth is 800 billion and Bill Gates’ net worth is 100 billion. So if your net worth is less 450 billion, the statement in the post is true.

The reason the statement above is mind blowing is that in this context you naturally think on a logarithmic scale, even if you don’t know what a logarithm is.

Or to put it another way, we think in terms of orders of magnitude. Musk’s net worth is an order of magnitude greater than Gates’, and Gates’ net worth would be an order of magnitude greater than that of someone worth 10 billion. Musk is a notch above Gates, and Gates is a notch above someone with a net worth around 10 billion, where a “notch” is an order of magnitude.

To put it another way, we think in terms of geometric mean √ab rather than arithmetic mean (a + b)/2 in this context. 100 billion is the geometric mean between 12.5 billion and 800 billion. Geometric mean corresponds to the arithmetic mean on a log scale. And on this scale, Gates is closer to Musk than you are, unless you’re worth more than 12.5 billion.

Here are three more examples of geometric means.

The size of Jupiter is about midway between that of earth and the sun; it’s the geometric mean. On a linear scale Jupiter is much closer to the size of the earth than the sun, but on a logarithmic scale it’s about in the middle. More on that here.

The tritone (augmented fourth) is half an octave. So, for example, an F# is in the middle between a C and the C an octave higher. Its frequency is the geometric mean of the frequencies of the two C’s. More here.

Finally, the humans body is a middle-sized object in the universe. From Kevin Kelly:

Our body size is, weirdly, almost exactly in the middle of the size of the universe. The smallest things we know about are approximately 30 orders of magnitude smaller than we are, and the largest structures in the universe are about 30 orders of magnitude bigger.

Proving you know a product

Posted on 24 January 2026 by John

There is a way to prove that you know two numbers a and b, and their product c = ab, without revealing a, b, or c. This isn’t very exciting without more context — maybe you know that 7 × 3 = 21 — but it’s a building block of more interesting zero knowledge proofs, such as proving that a cryptocurrency transaction is valid without revealing the amount of the transaction.

The proof mechanism requires an elliptic curve G and a pairing of G with itself. (More on pairings shortly.) It also requires a generator g of the group structure on G.

The prover takes the three secret numbers and multiplies the generator g by each, encrypting the numbers as ag, bg, and cg. When G is a large elliptic curve, say one with on the order of 2²⁵⁶ points, then computing products like ag can be done quickly, but recovering a from g and ag is impractical. In a nutshell, multiplication is easy but division [1] is practically impossible [2].

The verifier receives ag, bg, and cg. How can he verify that ab = c without knowing a, b, or c? Here’s where pairing come in.

I go more into pairings here, but essentially a pairing is a mapping from two groups to a third group

e: G₁ × G₂ → G_T

such that

e(aP, bQ) = e(P, Q)^ab.

In our case G₁ and G₂ are both equal to the group G above, and the target group G_T doesn’t matter for our discussion here. Also, P and Q will both be our generator g.

By the defining property of a pairing,

e(ag, bg) = e(g, g)^ab

and

e(cg, g) = e(g, g)^c.

So if ab = c, then e(g, g)^ab and e(g, g)^c will be equal.

[1] The literature will usually speak of discrete logarithms rather than division. The group structure on an elliptic curve is Abelian, and so it is usually written as addition. If you write the group operation as multiplication, then you’re taking logs rather than dividing. The multiplicative notation highlights the similarity to working in the multiplicative group modulo a large prime.

[2] The computation is theoretically possible but not possible in practice without spending enormous resources, or inventing a large scale quantum computer. This is the discrete logarithm assumption.

Author: John