Could Euler Have Solved This?
A new problem about the unit circle
Leonhard Euler needs no introduction. But let’s give him one anyway. He can be called the first truly modern polymath, one man who made foundational contributions to what are today considered widely disparate areas: graph theory, number theory, power series, complex analysis, harmonic numbers, and more. He made the first key step toward the Riemann Hypothesis, proving that
which converts the distribution of primes, a discrete problem, into a problem of analysis. He and Nicolaus Copernicus are the only mathematicians or scientists commemorated in the Lutheran Calendar of Saints.
And of course the number 2.71828… represented by is named for him, although it was implicitly known to John Napier and used under different names by several others. Euler may have helped his own Matthew Effect by using the letter for it.
Instead of presenting some of Euler’s work, today we will do the opposite. We will pose an open problem that we feel could have been explained to him, and ask how he would have attacked it. Could he have solved it? We will try to find out, even though we currently cannot solve it ourselves. It is a simple problem about points on the unit circle, nothing more.
Why Euler? Well, he connected the unit circle and complex analysis to five fundamental constants of mathematics in his famous formula
The Chordal Product
Suppose we have a set of points on the unit circle. There are -choose- chords connecting each pair of points. Define the chordal product
which is just the product of the lengths of the chords. How can you maximize this product? When there are no constraints on , your intuition is correct: space the points equally as far apart as possible.
The maximum value of is , and is achieved by locating the points at the complex th roots of unity. This optimum is unique up to rotations.
To prove this, we show that the product of the lengths of the chords emanating from any one point is . Taking this product over all points then makes , but since each chord is double-counted, the final answer is .
Now consider the chords coming from the point in the complex plane. Taking to be the principal th root of unity, so the other points in are for to . Those points are the roots of the complex polynomial , so by the fundamental theorem of algebra,
(One can also observe that is the derivative of evaluated at .)
A second proof notes that the chordal product for the th roots of unity is the absolute value of
This is because the DFT matrix is a Vandermonde matrix whose entry, indexing from to , is . The matrix is unitary, meaning . Thus , so
The New Problem
Now suppose we bar any point in from the open interval in radians. When , this constraint prevents the equal-spread solution. Thus subject to this constraint, .
Problem. Find the maximum value of when and , and find an that achieves it.
We can also ask, what is the asymptotic growth of for fixed ? Although , it could still have growth. What may be surprising is that it does not have any “growth” at all:
For any fixed and all , .
Note that this means the chordal products crash to zero even faster than the reciprocal of the unconstrained answer . “Dude—what happened to my nice exponential growth?” We believe, but haven’t proved, that in fact they approach at the fastest possible rate:
Theorem 3 (?)
For any fixed there is a constant such that as .
Now let itself vary with . That is, consider where . I and Maurice Jansen, who obtained his PhD under me in 2006, and has since enjoyed postdocs in Aarhus, Beijing, and currently Edinburgh with Rahul Santhanam, worked out that if we could keep whenever , then we could improve some lower bounds by Ran Raz and by Peter Bürgisser and Martin Lotz. These bounds concern arithmetical circuit families whose numerical constants are bounded in size.
We had thirty pages of work all set to go, pending the needed estimates. Unfortunately we guessed wrong—or at least I did, while Maurice proved:
When , , for any constant .
However, when , there exists such that for all , .
Likewise unfortunately, having was no good for our complexity-bound machinery. We have not been able to close the gap between and in the exponent, on exactly where the chordal product approaches faster than . What is so special about versus here, anyway?
What Would Euler Do?
If we had a closed-form expression for then all this asymptotic mystery would be lifted. Or it might be—it would depend on how nasty the expression came out to be.
How would Euler have attacked this problem? We can make facile guesses that he would have tried to express as a sum-of-products, since has that form as a determinant. Or he might have used power series or infinite sums like , where might depend on and in some hopefully-simpler manner than itself. He might have treated it as a problem in analysis, regarding the constraint as first breaking the circle and then deforming it.
I have been unable to locate anything like this simple problem in the literature, and have wondered why. The closest known problem that has been suggested to me is the Thomson spheres problem. This also sounds simple and turns out to be complex, even though it does not have the “missing bite” feature. That feature may be the historical cause of the problem being overlooked. People have been motivated by problems that are natural, but Nature does not arbitrarily exclude matter from some region of space. Perhaps it is only computation theory that brings “unnatural” motivations.
We have tried one thing that Euler couldn’t do: unleash computers on the problem. One can try standard heuristics of starting with a given and perturbing its points, retaining sets that increase the chordal product. However, a student who did so reported to me that numerical precision issues quickly prevented him from getting interesting results even for about . He tried writing in C with the Gnu MP Library for arbitrary (as-needed) precision, but computation quickly became too slow. This speaks to why the problem may ultimately be difficult.
The DFT: An Incredible Balancing Act?
Let’s go back to the original unconstrained problem, and ask how we might estimate , without using either of the above proofs of growth. Here is a rough “Fermi-style” estimate: The chords go from to on average, and so an “average” chord has length . Hence estimate as:
Of course this is a great over-estimate, and the flaw is easy to see: While long chords have length at most , short chords can have lengths approaching .
This does mean, however, that a tendency of long chords to produce is balanced by a cabal of short chords that produce . When a slice of the circle is excluded, almost however thin, the points in are driven closer together, causing more enough shorter chords to tip the balance of power to the cabal, so that dominates all. If the circle is inflated slightly, then we can expect the positive growth tendency to prevail. Thus the actual nearly-linear growth in the exponent is an exquisitely fine balance between the two tendencies.
The effect shows even better upon taking logarithms. For large and any ,
can be grouped into sub-expressions that contribute for all , . Here means that the “constant” may contain factors of . The upshot is that when , for all other than , every term is magically canceled by another term . All of the large magnitudes involving long and short chords cancel, leaving a residue of .
We would be interested to hear if—and how—other literature has presented the Discrete Fourier Transform as a study in huge cancellations, or has traced this as the “cause” of numerical-instability issues that are associated to it. Are there cases in Nature described by formulas that can be said to result from huge cancellations? We speculate on this in connection with renormalization in quantum field theory. Even more speculatively, we note that “rough” estimation from quantum-field theory gives a value for the energy content of our vacuum that is more than 120 orders of magnitude higher than the measured value reflected in our tiny-but-definitely-positive cosmological constant. Is there a chance that this value reflects the built-in nature of the Fourier Transform rather than mere multiversal chance?
Would Euler have solved the problem of computing Can you solve it? Can you at least approximate it asymptotically for values as ?
[fixed a jagged line]