The difficult proof of the corrected Sister Beiter conjecture

Cyclotomic Polynomials

The \(n\)-th roots of unity are the solutions of the equation \(x^n-1=0\). Except for \(n=1\) the polynomial \(x^n-1\) is always reducible, for example \(x^4-1=(x^2+1)(x+1)(x-1)\). One can wonder how \(x^n-1\) factors into irreducibles over \(\mathbf Z[x]\). The answer is given by $$x^n-1=\prod_{d\mid n}\Phi_d(x).$$ Here \(\Phi_d(x)\) is the \(d\)-th cyclotomic polynomial. The \(\Phi\) is a circle with a line through it and fits well to “cyclotomy” which comes from the Greek and means circle cutting. For each root of unity \(\zeta\), there is a lowest exponent \(n\) with \(\zeta^n=1\), it is said that \(\zeta\) is a primitive \(n\)-th root of unity. These are the roots of \(\Phi_n(x)\) all with multiplicity one. The polynomials \(\Phi_n(x)\) can be computed recursively from the above equation, we can also obtain it from the equations $$\Phi_n(x)=\prod_{\substack{1\le r\le n\\ \gcd(r,n)=1}}(x-\exp(2\pi i\tfrac{r}{n}))=\prod_{d\mid n}(x^d-1)^{\mu(n/d)},$$ where \(\mu(n)\) is the Möbius function. We have \begin{align*}\Phi_1(x)&=x-1\\ \Phi_2(x)&=x+1\\ \Phi_3(x)&=x^2+x+1\\ \Phi_4(x)&=x^2+1\\ \Phi_5(x)&=x^4+x^3+x^2+x+1\\ \Phi_6(x)&=x^2-x+1\\ \Phi_7(x)&=x^6+x^5+x^4+x^3+x^2+x+1\\ \Phi_8(x)&= x^4+1\end{align*} These polynomials have coefficients in \(\{-1,0,1\}\), and this is true for every \(n<105=3\cdot5\cdot7\). \(\Phi_{105}(x)\) has degree 48 and all its coefficients are in \(\{-1,0,1\}\), except for the terms \(-2x^7\) and \(-2x^{41}\).

In reality the coefficients of the cyclotomic polynomials are very complicated. The complexity as far as coefficients is concerned does not depend on the size of \(n\), but on the number of its different odd prime factors. An example is shown in the figure

Representation of the coefficients of a cyclotomic polynomial

Some properties of the cyclotomic polynomials

The degree of \(\Phi_n(x)\) is the number of primitive \(n\)-th roots of unity, so equal to the totient function of Euler \(\varphi(n)\). The coefficients of the polynomial $$\Phi_n(x)=\sum_{k=0}^{\varphi(n)}a_n(k) x^k$$ are symmetrical functions of the roots. For fixed \(k\) there are expressions of \(a_n(k)\) in terms of the Möbius function \(\mu(\cdot)\).

For \(n\ne 1\) the cyclotomic polynomials are self-reciprocal, that is, \(a_k=a_{\varphi(n)-k}\) or equivalently \(\Phi_n(x)=x^{\varphi(n)}\Phi_n(1/x)\). It follows that for \(n\ge 2\) the trigonometrical polynomials \(f_n(\theta)=e^{-\pi i\varphi(n)\theta}\Phi_n(e^{2\pi i \theta})\) are real functions. In the figure we represent these polynomials for \(3\le n\le 15\)

The functions  f_n(theta) for  2< n <16  and 0 < \theta< 1

We see that there are some points where several polynomials pass through. What are these points and what polynomials pass through each of these points? (A good exercise).

For \(p\mid n\) we have \(\Phi_{pn}(x)=\Phi_n(x^p)\), applying this we see that the non-zero coefficients of \(\Phi_n(x)\) are the same as those of \(\Phi_m(x)\) where \(m\) is the radical of \(n\), that is the product of the prime factors of \(n\). Also \(\Phi_{2n}(x)=\Phi_n(-x)\), hence the study of the coefficients reduce to the case in which \(n=p_1p_2\cdots p_r\) is a product of several different odd primes.

Since the coefficients are difficult to understand we consider its maximum \(A(n)\), where $$\Phi_n(x)=\sum_{k=0}^{\varphi(n)} a_kx^k,\qquad A(n)=\max_{0\le k\le \varphi(n)}|a_k|.$$ A polynomial is flat when \(A(n)=1\). When \(n=pq\) is the product of two primes we have \(A(pq)=1\). In fact there is an easy way to write the polynomial \(\Phi_{pq}(x)\). For example to write \(\Phi_{5\cdot7}\) construct the following table
\[\begin{array}{|rrr|rr|} \hline
30&2&9&16&23\\
25&32&4&11&18\\
20&27&34&6&13\\
15&22&29&1&8\\ \hline
10&17&24&31&3\\
5&12&19&26&33\\
0&7&14&21&28\\ \hline
\end{array}
\]
To build the table we start with a 0 at the lower left corner. Add a \(7\) at each step to the right and a \(5\) at each step up. Always taking the result modulo \(35=5\times7\). Then we draw one vertical and one horizontal line leaving just the number 1 at the vertex, as shown in the figure. Thus we have four rectangles of numbers. The numbers in the lower left rectangle are the exponents that carry a coefficient 1 in \(\Phi_{5\times7}\). The numbers in the upper right rectangle are the exponents of the terms that carry a coefficient \(-1\). The numbers in the other two rectangles correspond to zero coefficients. So we can write the polynomial \(\Phi_{35}\) $$\Phi_{35}(x)=x^{24}-x^{23}+x^{19}-x^{18}+x^{17}-x^{16}+x^{14}-x^{13}$$ $$+x^{12}-x^{11}+x^{10}-x^8+x^7-x^6+x^5-x+1$$ This trick is the \(p\times q\) LLL-diagram (due to H. W. Lenstra, Jr, T. Y. Lam and K. H. Leung).

Sister Marion Beiter conjecture

It is difficult to find information about Sister Marion Beiter. She was born in 1907 in Buffalo, and was educated at the Buffalo Academy of the Sacred Heart, a Catholic girls’ school directed by nuns. At the age of 16 she entered the order and at 22 she took her final monastic vows. She began as a teacher in private parochial schools. She graduated at the age of 37 and became head of the mathematics department of the private university for girls that her order opened at that time in New York. She obtained her doctorate at the age of 53: Coefficients in the cyclotomic polynomial for numbers with at most three distinct odd primes in their factorization. Prof. Pieter Moree explain how Prof. H.W. Lenstra meets Sister Marion Beiter. Lenstra always had an interest in cyclotomic polynomials and published on it. In his early career he was professor at the University of Amsterdam. At some point a nun knocked at his door. It was Sister Marion Beiter, who was on holiday in Amsterdam. So they chatted a bit. She knew about his work and so she had decided to try to speak to him.

The polynomials \(\Phi_p(x)\) and \(\Phi_{pq}(x)\) for primes \(p<q\) have coefficients in \(\{-1,0,1\}\). The ternary polynomials \(\Phi_{pqr}(x)\) (with \(p<q<r\) primes) are the next case to consider. A. S. Bang proved that \(A(pqr)\le p-1\). Therefore we may define the quantity $$M(p)=\max_{p<q<r \text{ primes}} A(pqr)$$ Also he showed that \(M(3)=2\). There is an algorithm to compute \(M(p)\) but it is not practical. Our actual knowledge reduces to the cases $$M(3)=2, M(5)=3, M(7)=4, M(11)=7, M(13)=8, M(19)=12.$$ Sister Marion Beiter proved that \(M(5)=3\) and \(A(pqr)\le (p+1)/2\) when \(q\) or \(r\) is congruent to \(\pm1\bmod p\). She made the conjecture that \(M(p) \le (p+1)/2\) and proved it for \(p=5\). However, Y. Gallot and P. Moree (2009) disproved her conjecture for every \(p\ge 11\). In fact, they proved that \(M(p)\ge (2/3-\varepsilon)p\) for \(p\) large enough, a result that together with numerical evidence inspired them to suggest the Corrected Sister Beiter conjecture stating that \(M(p) \le 2p/3\).

Chinese insight: Jia Zhao and Xianke Zhang

Jia Zhao and Xianke Zhang of Tsinghua University published in 2010 a paper proving that \(M(7)= 4\). At that time it was known that the conjecture of Sister Beiter was true for \(p=3\) and \(5\) and false for \(p\ge 11\), so \(p=7\) was the missing case. For this they get a condition for the corrected Beiter conjecture to be true, and show this condition is satisfied for \(p=7\).

The paper of Jia Zhao and Xianke Zhang showing that \(M(7) = 4\), was received by the editors in January 2009 and published in June 2010, which is a reasonable time lapse. They went on to generalize their method to all primes and posted in arXiv a preprint on it in October 2009. They sent it to a journal, we only know that their paper was never published in a journal.

Pieter Moree and his students

Pieter Moree (1965–) is a Dutch mathematician, now at the Max Plank Institute of Mathematics, he works on number theory. He has many papers dealing with the cyclotomic polynomials. In his web page he says Thanks to intern projects I got also interested in cyclotomic polynomials (especially the behavior of their coefficients) and their connection with numerical semigroups. In particular he with Y. Gallot stated the Corrected Beiter conjecture that we are considering here.

A group of students, first Branko Juran and Adrian Riekert in 2015, and later David Schmitz and Julian Völlmecke in 2022 under the direction of Pieter Moree read the paper and started to work on writing up a more legible version of the “proof” of Jia Zhao and Xianke Zhang. They have posted a paper in arXiv in which they prove the corrected sister Beiter conjecture.

Perhaps reading the above you might think that they have not done much more than read the proof of Zhao and Zhang. Not so fast, Moree tells us … the original article by Zhao and Zhang is quite unreadable. Many years ago I tried to understand it, but gave up. That is kind of intriguing, as in essence it only uses math not going beyond first year student level, I would say. It has never become clear to me what makes the proof tick, what its philosophy is.

In the preprint of Zhao and Zhang the proof start assuming some relations between the primes \(p\), \(q\) and \(r\) and then says by Remark 1, we can observe that the proof is similar for the other cases. Then Remark 1 do not exists, possibly they speak of Remark 2.6 but even then it is not clear to me what would happen in the other cases. In the revised version of Moree and his students there are not similar proofs for different cases, but all cases are reduced to one.

The proof is not a direct counting of the numbers of \(-1\)’s and \(1\)’s, instead several subsets of \(\mathbf Z/p\mathbf Z\), that is of the \(0\le v\le p-1\) are separated representing \(1\)’s or \(-1\)’s. Then some injective functions from one on other sets are defined making some sets smaller than others. In Zhao and Zhang this is not said clearly. It is made explicit in the new version.

Referee’s nightmare

The paper of Zhao and Zhang can be defined as a referee’s nightmare. Almost illegible but not clearly false, and claiming to have proven an important result. The problem is that the present proof is difficult to expose.

In theory, the Copyright laws purpose is to protect the rights of the authors. In practice, all that is achieved is to prevent authors from making any profit from their work. Authors are required to waive their rights in order to obtain publication of their work. All the benefits, and they are not few, are taken by the multinationals that make this extortion to the authors.

The greatest satisfaction of a mathematician is to see his theorems used by others to solve new problems. Copyright laws only make it more difficult to achieve this goal, making their works inaccessible to many. I would like all mathematical publications to be free. I am delighted that my book on Carleson’s theorem can be freely downloaded on some unauthorized sites. This is why I am such a fan of arXiv. Many thanks to Alexandra Elbakyan, who has done so much for science in general and mathematics in particular.

But if we have to live in a capitalist world, there are other possible worlds: A world in which referees are well paid, acknowledged at the head of the published paper. His work is to check any step and give credit to the paper. To be referee of a paper should count almost as much or even more than being an author. A referee should be as a final collaborator of a paper, but also a jury. (Perhaps until Lean or Lean+AI can be the final check of a paper. I wrote an entry on Lean in this blog Artistic creation and mathematical creation.

A world in which every application of a theorem would give a benefit to its author. Every time a theorem were applied in a published article, the author of that theorem should receive an amount as remuneration. This remuneration should be paid by the institution of the mathematician who applies the theorem. Perhaps to avoid abuses the referee (well paid) should certify that the theorem is necessary in the argument.

But immediately a thousand schemes come to mind to misuse these well-intentioned ideas. Probably it is better a world in which the author’s satisfaction is only to see his theorems known and applied in the solution of new problems.

Learn more

Cyclotomic polynomials are easy to understand and filled with problems and questions. A good introduction to some of its properties is found in the paper by Moree in the Dutch popular journal for Mathematics Nieuwe Archief voor Wiskunde. Some of its papers are in Dutch but many in English

Pieter Moree, Prime gaps and cyclotomic polynomials, Nieuwe Archief voor Wiskunde, 22 (2021) 1-7.

The complete collection of NAvW can be find here.

There is also a survey on Cyclotomic Polynomials. It is hidden under a wall of money, but we have also the arXiv version:

C. Sanna, A survey on coefficients of cyclotomic polynomials, Expo. Math. 40 (2022) 469-494. arXiv:2111.04034.

The paper we comment today and its antecedent are in arXiv. The one by Juran et al. do not use complicated math but I can not say it is easy read (but not impossible for an undergraduate):

B. Juran, P. Moree, A. Riekert, D. Schmitz & J. Völlmecke, A proof of the corrected Sister Beiter cyclotomic coefficient conjecture inspired by Zhao and Zhang, arXiv:2304:09250. April 2023.

Jia Zhao & Xianke Zhang, A proof of the corrected Beiter conjecture, arXiv:0910.2770, September 2009.

Cyclotomic polynomials is a good topic for undergraduates. In 2008 Nathan Kaplan was awarded the Morgan prize to Outstanding Research in Mathematics by an Undergraduate Student for four papers one of them a paper where he proved that given prime numbers \(p<q\), there is an infinite family of prime numbers \(r\) such that \(A(pqr)=1\):

Nathan Kaplan, Flat cyclotomic polynomials of order three, J. Number Theory 127, (2007) 118-126.

The paper of Kaplan became very influential in the study of coefficients of cyclotomic polynomials. For example, Gallot and Moree in their disproof of Sister Beiter’s conjecture made crucial use of it.

Since it is written by an undergraduate, anyone can easily read it.

The leading figure is a representation of the cyclotomic polynomials \(\Phi_n\) for \(3\le n\le 13\) in the unit circle modified as said above.

I changed mind and use the x-ray of \(\Phi_{105}(z)\) instead

 

Be the first to comment

Leave a Reply

Your email address will not be published.


*