Javier Cilleruelo’s goal

At the beginning of last July, “El Confidencial” reported that this year the Spanish government forced its team to pay out of pocket for the trip to the Mathematical Olympics. These Olympics are an international competition where young high school students face quite complicated mathematical problems and challenges. It is a very prestigious competition, and it is not unusual for its winners to end up being shining stars of the mathematical universe; it is enough to mention here as examples the cases of Maryam Mirzakhani (the only woman to have won the Fields medal) or Terence Tao (possibly the best mathematician of the 21st century).

Leaving the six young Spanish mathematicians without funding to take part in the Olympics is a ridiculous cost, but this political decision has devastating effects on the social perception of mathematics. Moreover, it means continuing with the series of cutbacks of the last decade, which is doing so much damage to the incipient scientific take-off that Spain has been experiencing since the arrival of democracy. Some argue that we are a country that is thousands of years old, yet throughout all those centuries Spain has contributed practically nothing to mathematics. Possibly this has to do with what society passes on to children as their role models: Messi, Ronaldo,… and what society values: Easter, Fallas, Football,… For most of our history, anyone who has done something intellectually interesting, innovative, who thinks or writes, has been looked upon with suspicion. Here we are looking for docile citizens, believers, good, in the worst sense of the word good.

The problem of our scientific deficit is cultural, very deep and therefore difficult to overcome, and it reminds me of what happens with sexism in society: it is so deep in our bones that we do not see it. With this mental framework, the government decides to suppress aid to our young people to participate in the Mathematics Olympiads because it lacks scientific sensitivity and knows that it will have no political cost. In this, as in other areas of science, the comparison with other neighbouring countries is dramatic. In the case of the Mathematical Olympiads, one country stands out in particular: Hungary. And it is no coincidence that it is also a country with a genuine mathematical tradition, which in the last century has been substantiated by a good handful of top mathematicians: John Von Neumann, Paul Ërdos, Paul Halmos, George Polya, Gabor Szego,… (see my post The Happy end problem, where I discussed the subject of Hungarian mathematics).

Today’s post is very much about Hungary, and it will feature many good Hungarian mathematicians: Simon Sidon, Paul Erdös, Paul Turan, Miklós Ajtai, János Komlós, Endre Szemeredi, Imre Ruzsa (the latter, by the way, took part in several Mathematical Olympiads, winning a silver medal in 1969, and two gold medals in the successive competitions of 1970 and 1971, where he obtained a perfect score). However, the hero of the entry will be, on his own right, a Spanish mathematician: Javier Cilleruelo. Which goes to show that if mathematics were cared for and given prestige here, as it is in Hungary, things could be very different.

The problem I will deal with in this post was proposed by Simon Sidon, a Hungarian mathematician, who in 1932 posed the question of constructing a set of natural numbers \(a_1<a_2<\cdots\) such that the sums \(a_i+a_j\) (\(i\le j\)) are all distinct and at the same time as dense as possible.

When in 2013 Cilleruelo came to a congress in Sevilla he spoke about his construction of a Sidon set. His presentation was masterful. He went just into enough details for us to see the whole construction without getting lost.  I was strongly impressed, I hardly knew him but I went up to tell him how much I had enjoyed his talk. The Sidon sets are a purely Hungarian topic and that is why I say that Javier has scored a goal against Hungary. It was a confirmation that Spain was finally contributing something to mathematics (which is why the decision on the Mathematical Olympiad is so incomprehensible and worrying).

 

It is not a particularly recent construction, Javier’s work was published in 2014 in the journal Advances in Mathematics, but his passing (in 2016) reminded me of his construction and, partly as a tribute to a Spanish mathematician, I think this post is justified.

Mathematics is the human activity where imagination shines the brightest. The imagination contained in mathematical constructions surpasses by far that which can be seen in a painting, or a novel. I mean imagination, in the sense that a Bosch painting shows more imagination than a Mondrian composition.

Javier’s work is extensive, and we could talk about many other of his results, but I think this one shows the character of his work very well.

Sidon and his sets

The matter was raised by Simon Sidon and it is easy to understand. We are looking for sets \(A\), of natural numbers, such that all the sums \(a+b\) between their elements are different. For example with the numbers in \(A=\{0, 2, 7, 8, 11\}\) we can form the sums \(0+0=0\), \(0+2=2\), … \(8+11=19\), and \(11+11=22\), in total there are \(5+4+3+2+1=15\) sums, all of them different, which ordered from greater to lesser are
$$0,\ 2,\ 4,\ 7,\ 8,\ 9,\ 10,\ 11,\ 13,\ 14,\ 15,\ 16,\ 18,\ 19,\ 22.$$
We call Sidon sets those that have this property of distinct sums.

We can construct Sidon infinite sets. For example the set of powers of \(2\), \(P_2=\{1,2,4,8,16, \dots, 2^n,\dots\}\) is Sidon as we can easily verify. But this set has very few elements. If we denote by \(A(x)\) the cardinal of the set of elements of \(A\) which are \(\le x\), we will have that \(P_2(x)\le 1+\log_2x\). Sidon’s question to Erdös was how dense can we construct a Sidon set? Or, more concretely: what is the greatest power \(\alpha>0\) such that we can construct a Sidon set \(A\) such that \(A(x)>C x^\alpha\) for some constant \(C\) and all \(x>0\) (\(A(x)\gg x^\alpha\) for short). We will call the supremum of the \(\alpha\), the Sidon exponent.

Simon Sidon (1892-1941) studied mathematics, but worked as an actuary, however he took up mathematics as a hobby. He worked on trigonometric series, which led him to think about Sidon sets. Paul Erdös believed that Sidon had some mental problems. Once Paul Erdös and Paul Turán went to visit him at his house. They knocked at the door. He opened the door just a little and said to them: Please come another time to look for someone else. So what? Didn’t Erdös know that sometimes visitors are a nuisance. You know that Erdös had no profession, he went around giving lectures and settled down in every city he came to in the house of some mathematician to say: I have an open mind. Of course, he published in collaboration with them.

The exponent of Sidon is \(\le \frac12\)

There is an easy observation, let \(A\) be an arbitrary Sidon set, for each \(x>0\) let \(B=A(x)\). \(B\) is a Sidon set with \(n=A(x)\) elements. The set of sums \(\{b+b’\colon b, b’\in B\}\) is a set of \(1+2+\cdots +n=\frac{n(n+1)}{2}\) elements all distinct and lying in the interval \(0\le b+b’\le 2x\). Then
$$\frac{n^2}{2}<\frac{n(n+1)}{2}\le 2x,\qquad n\le 2\sqrt{x}.$$
That is \(A(x)< 2\sqrt{x}\). It is not possible to find Sidon sets with \(A(x)>2x^{1/2}\).

The exponent of Sidon is \(\ge\frac13\)

The Indian mathematicians Chowla and Mian proved in the other direction that there exist Sidon sets such that \(A(x)>x^{1/3}\). For this they used the greedy’s algorithm. They start from the set \(A=\{0\}\) and add terms successively, so that at each time the smallest number that makes the resulting Sidon set is added; thus they obtain the sequence
$$0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147, 181, 203, 251, 289, 360, 400, 474, $$
For example, once \(\{0,1,3\}\) has been constructed, the next number cannot be a four because \(\{0,1,3,4\}\) is not Sidon (\(0+4=3+1\)), nor is \(\{0,1,3,5\}\) a Sidon set (\(5+1=3+3\)), nor is \(\{0,1,3,6\}\) (since \(0+6=3+3\)). But on the other hand, the set \(\{0,1,3,7\}\) is Sidon, as can be easily checked. So \(7\) is the next term of the sequence. Thus the following terms \(12\), \(20\), \(30\), \(44\),… are also generated.

If we analyse the previous process, the condition on \(a_n\) is that it is not equal to any of the numbers \(a_i+a_j-a_k\) with \(0\le i, j, k\le n-1\). This is to avoid \(n^3\) numbers. It is certain that among the numbers \(0\le a\le n^3\) (which in total are \(n^3+1\)) there is one that is different from any of the \(a_i+a_j-a_k\). \(a_n\le n^3\).

Fixed \(x>0\), we look for \(n\) such that \(n^3\le x<(n+1)^3\). We then know that \(a_0=0\), \(a_1\), \(\dots\), \(a_n\le x\). That is to say that \(A(x)\ge n+1\ge x^{1/3}+1\). Then the Sidon exponent \(\alpha\) verifies \(\frac13\le \alpha\le \frac12\).

Erdös Conjecture

Erdös conjectured that the exponent of Sidon is \(\frac12\). This means that for every \(\varepsilon>0\) there will exist a Sidon set with \(A(x)\gg x^{1/2-\varepsilon}\). Together with Rényi they proved that there exists a set \(A(x)\gg x^{1/2-\varepsilon}\) such that it is almost Sidon in the sense that for every \(m\) the set of solutions of \(a_j+a_k=m\) is finite.

The Chowla and Mian sequence obtained with the greedy’s algorithm was for 50 years the densest known infinite Sidon set. The record was broken in 1981 by Atjai, Komlós and Szemerédi who proved that there exist Sidon sequences such that \(A(x)\gg (x\log x)^{\frac13}\). The construction was random and used results from graph theory.

Ruzsa construction

Ruzsa in 1998 succeeded in breaking the \(1/3\) exponent barrier and constructed Sidon sets such that \(A(x)\gg x^{\sqrt{2}-1-\varepsilon}\) (for any \(\varepsilon>0\)). Ruzsa’s construction uses very innovative ideas.

The most original idea is the use of prime numbers. The set of prime numbers \(\mathcal P\) has Sidon’s property with respect to the product. That is, if \(p_j\) are prime numbers such that \(p_1p_2=p_3p_4\) then it must necessarily follow that \(\{p_1,p_2\}=\{p_3,p_4\}\). We can get closer to Sidon’s property if we take logarithms: the set \(\{\log p\colon p\in\mathcal P\}\) has Sidon’s property, but it does not consist of integers.

Rusza’s construction begins by choosing a real number \(1\le r\le2\) to form with them the numbers \(r\log p\). These he develops in binary and with the digits of this number he constructs another of size \(p^{\sqrt{2}+1}\). This is not a simple construction. It is finally proved that for almost any \(r\) and by removing only a small number of terms a Sidon sequence is obtained.

Javier’s construction also obtains an infinite set of Sidon with this density, but with the enormous advantage that the construction is effective, not random like Rusza’s. This can be a huge advantage if we want to use Sidon sets for a specific purpose.

The genetics of Sidon sets

The property of a Sidon set \(A\) is that each sum \(a+b\), uniquely determines the elements \(a\) and \(b\) that compose it. It is as if \(a+b\) were a descendant of \(a\) and \(b\). The set is Sidon’s if each sum contains the genetic information that allows to determine the parents \(a\) and \(b\).

In the Cilleruelo construction each term will be associated with a prime number. So the Sidon set will be
$$A=\{a_2, a_3, a_5, a_7, a_{11}, \dots\}.$$
The information of each term is thus identified by a prime number. Knowing \(a_p+a_q\) we must be able to determine the pair of primes \(\{p,q\}\) that generates it. This information will be contained in the digits that make up \(a_p\) and \(a_q\). The main problem is that these digits are added together and we need to make sure that this information is not lost in the process.

Javier needs to ensure two things:

• Construct a relatively dense sequence.
• That it has Sidon’s property.

and manages to separate the two problems. So that the solution of one does not interfere with the other.

Construction of the dense succession

The main idea to obtain the density of the sequence is to determine the digits that each element \(a_p\) of the sequence will have. But they will not be the digits in base 10, instead it will be convenient to introduce a generalised base, similar to the way we measure time using a scale of seconds, minutes, hours, days, years, etc. Each unit being a multiple of the previous one.

Generalised bases

In order to get a dense sequence, he will use the representation in a base. We are used to represent each number in base \(10\). Given a natural number \(n\) we look for the unique exponent \(k\) such that \(10^{k-1}\le n<10^{k}\). We then divide \(n=\alpha_{k}10^{k-1}+n’\) with \(n'<10^{k-1}\). The first digit of \(n\) is then \(1\le \alpha_{k}<10\) and we continue the process with \(n’\). In this way the digits of the number \(n\) are generated.

Cilleruelo uses a modification of this process, substituting the powers of \(10\) with products

$$N_1,\quad N_1N_2,\quad N_1N_2N_3,\quad N_1N_2N_3N_4,\quad \dots$$
Given \(n\) we will find \(k\) such that
$$N_1N_2\dots N_{k-1}\le n<N_1N_2\dots N_{k-1}N_k$$
and the division will give us the first digit \(n=\alpha_kN_1N_2\cdots N_{k-1}+n’\). Being here \(1\le \alpha_k< N_k\), \(n'<N_1N_2\cdots N_{k-1}\). Continuing the process with \(n’\).

Now the number will be represented by the digits \(\alpha_k\alpha_{k-1}\dots\alpha_1\) being
$$0\le \alpha_j \le N_j,\qquad n=\alpha_kN_1N_2\cdots N_{k-1}+\cdots
+\alpha_jN_1N_2\cdots N_{j-1}+\cdots+\alpha_1.$$

Javier can choose the \(N_k\). He takes \(N_k=4q_k\) for certain numbers \(q_k\).
He will restrict his numbers \(a_p=\alpha_k\alpha_{k-1}\cdots \alpha_1\), so that their non-zero digits satisfy the inequalities
$$q_j+1\le \alpha_j\le 2q_j-1.$$
Thus, by adding \(a_p=\alpha_k\alpha_{k-1}\dots \alpha_1\) and
\(a_{p’}=\beta_\ell\beta_{\ell-1}\dots \beta_1\) we will have
$$2q_j+2\le \alpha_j+\beta_j\le 4q_j-2,\qquad \text{si $j\le \min(k,\ell)$}.$$
This means that to add two of these numbers we only have to add the corresponding digits (we do not take units from one magnitude to the next).

Also knowing the sum \(a_p+a_{p’}\) we can say that we have added two numbers, one with \(k\) digits and the other with \(\ell\) digits. For example \(\ell\) will be the order of the largest digit of the sum that is \(\ge2q_j+2\). It is as if in base 10 we restrict ourselves to numbers with digits \(3\), and \(4\),
$$43343+344=43687.$$
When adding, we only have to add the digits, and we also know that a 3-digit number and a 5-digit number have been added, because the first three digits of the sum are \(\ge6\). And the sum has 5 digits.

Choice of the \(q_j\) and the size of the \(a_p\)

Bertrand’s postulate states that given \(x>1\) there always exists a prime number \(x<p\le 2x\). This is nowadays a theorem, thanks to which we can choose the numbers \(q_1\), \(q_2\), \(\dots\) that appear in our base as the smallest prime numbers contained in the intervals
$$2^{2j-1}<q_j\le 2^{2j+1}, \qquad j\ge1.$$
The first ones are
$$q_1=3,\ q_2=11,\ q_3=37,\ q_4=131,\ q_5=521,\ q_6=2053,\ q_7= 8209,\ q_8= 32771,\ q_9= 131101,\dots\ $$
Now we have to say which are the \(a_p\) (the construction will not give us any element when \(p=q_j\), so we eliminate from the sequence the terms \(a_{q_j}\). As the \(q_j\) grow exponentially they have no influence on the density of the sequence \(a_p\), but we will not return to this unimportant detail).

From this point on, the construction of Cilleruelo depends on a parameter \(\frac13\le c\le \frac12\) on which the density of the sequence will depend in the end.

The idea is to take the numbers \(a_p\) growing with \(p\). In particular the number of digits of \(a_p\) in the base \((4q_j)\) is going to grow with the size of \(p\) Thus we will have
$$a_p=x_k(p)\dots x_1(p)$$.
where \(x_j(p)\) is the \(j\)-th digit of \(a_p\) in the base \((4q_j)\).

More precisely \(a_p\) will have \(k\) digits precisely if

$$p\in \mathcal P_k:=\Bigl\{p \text{ prime}\colon \frac{2^{c(k-1)^2}}{k-1}
<p\le \frac{2^{ck^2}}{k}\Bigr\}.$$
It is easy to prove that with this choice the set \(A\) satisfies the condition \(A(x)=x^{c+o(1)}\). But the most important part of the construction is still pending. How to guarantee that the set \(A=\{a_p\colon p \text{ prime}\}\) satisfies Sidon’s condition.

Choice of digits. Property of Sidon

Choice of digits

If \(p\in \mathcal P_k\) we will have \(a_p=x_k(p)\dots x_1(p)\). The digits \(x_j(p)\) must carry information about the prime \(p\) so that this information can be retrieved (to some degree at least) when we only know the sum \(x_j(p)+x_j(p’)\). The information is going to be related to the prime \(q_j\). The idea is that \(x_j(p)\) carries the class information of \(p\) modulo \(q_j\).

But we cannot simply take \(x_j(p)=p\mod q_j\). Since adding would lose the information, \(x_j(p)+x_j(p’)\) is information about \(p+p’\) and, in general, there are many pairs of primes with the same sum. That does not happen with the product. If we could recover \(pp’\), this does uniquely determine the factor pair.

I. e. when adding up the numbers we have to get information about the product of the primes. This is achieved with the logarithm. Here we have to use the logarithm substitute for congruences.

This is why Cilleruelo uses that, given \(q_j\), there exists a primitive root \(g_j\). An element such that the powers \(g_j\), \(g_j^2\), \(\dots\), \(g_j^{q_j-1}\) are all non-zero classes modulo \(q_j\). This means that since \(p\) is not divisible by \(q_j\), there exists a \(2\le a\le q_j \) such that \(p\equiv g_j^{a}\pmod{q_j}\) and we will take then \(x_j(p)=a+q_j-1\). Thus as \(g_j^{q_j-1}\equiv1\pmod{q_j}\), we have
$$g_j^{x_j(p)}\equiv p\mod q_j, \qquad q_j+1\le x_j(p)\le 2q_j-1.$$

What have we achieved? Suppose we add \(a_{p_1}\) with \(k\) digits and \(a_{p_2}\) with \(\ell<k\) digits, we will have

\begin{align*}
a_{p_1}+a_{p_2}&=x_k(p_1) x_{k-1}(p_1)\dots x_\ell(p_1)\dots x_1(p_1)+
x_\ell(p_2)\dots x_1(p_2)\\
&=x_k(p_1) x_{k-1}(p_1)\dots x_{\ell+1}(p_1)[x_\ell(p_1)+x_\ell(p_2)]\dots
[x_1(p_1)+x_1(p_2)]
\end{align*}
Knowing the sum we would know:

• The magnitude of the digits tells us that we have added a number \(a_{p_1}\) of \(k\) digits with another \(a_{p_2}\) of \(\ell\) digits..
• For \(1\le j\le \ell\) we would know that
  $$g_j^{x_j(p_1)+x_j(p_2)}\equiv g_j^{x_j(p_1)}g_j^{x_j(p_2)}\equiv
  p_1p_2\pmod{q_j}$$
• For \(\ell<j\le k\)
  $$g_j^{x_j(p_1)}\equiv p_1\pmod{q_j}$$

This means that we know
$$p_1p_2\pmod{q_1\cdots q_\ell},\qquad p_1\pmod{q_{\ell+1}\cdots q_k}.$$

If it were \(k=\ell\) this would be enough to know \(p_1p_2\) and therefore by factoring, we know \(p_1\) and \(p_2\). In the general case the reasoning is more complicated and requires the use of the dimensions we know of \(q_j\).

Assuming that there were two equal sums \(a_{p_1}+a_{p_2}=a_{p’_1}+a_{p’_2}\), Javier proves that we would have

$$(1-c)k^2<\ell^2<\frac{c}{1-c}k^2.$$

Sidon sets

It follows from the above that if \(A\) is not a Sidon set the following inequality must be true
$$1-c<\frac{c}{1-c} \text{ lo que equivale a } c<\frac{3-\sqrt{5}}{2}=0.3819\dots.$$
Therefore the construction, taking \(c=\frac{3-\sqrt{5}}{2}\), gives us a Sidon set. This is the first example of an explicit Sidon sequence with counter function \(A(x)\gg x^c\) for some \(c>\frac13\).

End of the discussion

At this point, there seems to be nothing to do. If we want a denser sequence we must take \(c>\frac{3-\sqrt{5}}{2}\) and we have seen that in that case the constructed sequence contains coincident sums \(a_{p_1}+a_{p_2}=a_{p’_1}+a_{p’_2}\). Javier examines these cases and determines that if a prime \(p_1\) appears in one of these sums, then it belongs to a special set of primes. He then shows that these primes are rare, that is, they do not alter the density if and only if \(\frac{2c}{1-c}-1\le c\). That is, for any \(c=\sqrt{2}-1-\varepsilon\) with \(\varepsilon>0\).

It is a great surprise that the very different method leads to the same density as Rusza’s probabilistic method. Perhaps Erdös’ conjecture is not true and Sidon’s exponent is \(\sqrt{2}-1\)?

 

Learn more

Javier’s full paper is freely downloadable on the web, and does not use advanced mathematics.

J. Cilleruelo, Infinite Sidon sequences, Advances in Math., 255 (2014) 474-486.

A very complete annotated bibliography on the Sidon sets can be found at

K. O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Elect. J. Combinatorics #DS11: July 26, 2004.

The Gaceta de la Real Sociedad Matemática Española dedicated issue 3 of volume 19 (2016) to Javier. It contains articles by his collaborators but is not in open access. (Now, in 2022, La Gaceta is open access.  Including the number dedicated to Javier)

There are many obituaries, which explain part of his personality:

• Adolfo Quirós on el País
• Antonio Córdoba on El Mundo
• Manuel de León on Matemáticas y sus Fronteras
• Blog Gaussianos