# Combinatorial Technique in Selberg's Symmetry Formula

Before I ask my question, I would like to inform, I am new to this topic from a non-math background, I am trying to understand the topic.

In Selberg, A. (1949). An Elementary Proof of the Prime-Number Theorem the author derived a formula, which is know as "Selberg's Symmetry Formula" or "Selberg's Lemma":

$$\sum_{p \leq x} \log^2 p + \sum_{pq \leq x} \log p \log q = 2x\log x + O(x)$$

In the paper entitled "A Computational History of Prime Numbers and Riemann Zeros" (on page 4, click here) it is written about "Selberg’s symmetry formula" that-

Until 1950 it was widely believed (e.g., by Landau) that no such elementary proof could be developed and so this result greatly impressed the contemporaries. Later Selberg extended this (Selberg's Symmetry Formula) combinatorial technique to show the PNT for primes in arithmetic progression, see [68]. For a nice survey see Diamond [18]. Unfortunately, the high hopes placed in new insights coming from finding an elementary proof of PNT were thwarted.

In the second page of the article "On elementary proofs of the Prime Number Theorem for arithmetic progressions, without characters" by Andrew Granville, it is written -

My questions are following revolving around the significance of this formula (thus asking in a single post) :

BOUNTY QUESTION

We read, that "Selberg's Symmetry Formula" is a Combinatorial Technique and can be extended to show the PNT for primes in arithmetic progression, how "Selberg's Symmetry Formula" is a Combinatorial Technique and how it is extended to show the PNT for primes in arithmetic progression?

If there are books, research-papers, lecture sheets where this combinatorial technique and motivation are discussed, please mention in the comment.

1. What does the formula/lemma tell? The equivalent question is, what is the motivation or significance of this formula?

2. Why it is called "Symmetry Formula" (the motivation behind naming)?

3. This is the Selberg's Formula given in the book Apostol's "Analytic Number Theory" book: $$\psi(x)\log x+\sum_{n\leq x}\Lambda(n)\psi\bigg(\dfrac xn\bigg)=2x\log x+\mathcal O(x),$$ how it is obtained from $$\sum_{p \leq x} \log^2 p + \sum_{pq \leq x} \log p \log q = 2x\log x + O(x)$$?

• I'm not sure what sort of answer you're looking for. It's an asymptotic expression for a sum of a well-behaved, fairly slowly varying function over primes $\leqslant x$, thus it's not surprising that it can tell us something about the distribution of primes. In fact, one can derive the PNT (at least the basic form without error bounds) from it, so it tells us rather much about the distribution (but so far I haven't seen a proof that made it transparent to me how it works, in contrast to the complex analytic proofs). – Daniel Fischer Oct 3 '20 at 20:44
• I don't know about the "combinatorial trick", unless that means use of the Möbius function (and it's easier to first prove the form with $\psi$). – Daniel Fischer Oct 3 '20 at 20:45
• @DanielFischer read the proof (source: math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Balady.pdf), except 1 part (see the post: math.stackexchange.com/questions/3859514/…), understood everything, but I don't see anything combinatorial, I also read the "Selberg’s asymptotic formula" in the book IntroductiontoAnalytic Number Theory by of Tom M. Apostol,skimmed through Selberg's original paper, nothing about combinatorics is mentioned. Could you plz point out which part is combinatorial in Selberg's Symmetry Formula? – Consider Non-Trivial Cases Oct 12 '20 at 12:19
• I don't know what is considered combinatorial in it. Perhaps reading Erdős's paper referenced by Granville will shed light on it. – Daniel Fischer Oct 13 '20 at 9:52
• @DanielFischer Erdos's paper tells nothing. – Consider Non-Trivial Cases Oct 16 '20 at 8:39

Note: Here I give an answer to the first part of the bounty question, admittedly rather a personal interpretation than based on solid facts.

Combinatorial techniques enable combinatorial proofs. These are proofs which provide a bijection between the elements of a known set and the elements of the set under consideration.

In What is a combinatorial proof exactly? one of the answers contains a citation of what a combinatorial proof is about from R.P. Stanley.

In order to find an indication for the usage of combinatorial techniques I'd like to point to A. Selberg's paper An elementary proof of the prime number theorem from 1949.

We find in A. Selberg's paper that his proof of his symmetry formula (2.6) \begin{align*} \sum_{p\leq x}\log^2 p + \sum_{pq\leq x}\log p \log q =x\sum_{d\leq x}\frac{\mu(d)}{d}\log^2\frac{x}{d}+\mathcal{O}(x)\tag{2.6} \end{align*} is based upon estimating $$\sum_{n\leq x}\theta_n$$ in two different ways. As stated in (2.1) he uses the notation $$\theta_n=\sum_{d|n}\lambda_d$$ and $$\lambda_d=\mu(d)\log^2 \frac{x}{d}$$.

One way: He obtains in (2.4) \begin{align*} \color{blue}{\sum_{n\leq x}}&\color{blue}{\theta_n}=\sum_{n\leq x}\sum_{d|n}\lambda_d =\sum_{d\leq x}\lambda_d\left[\frac{x}{d}\right]\\ &=x\sum_{d\leq x}\frac{\lambda_d}{d}+\mathcal{O}\left(\sum_{d\leq x}\left|\lambda_d\right|\right) =x\sum_{d\leq x}\frac{\mu(d)}{d}\log^2\frac{x}{d}+\mathcal{O}\left(\sum_{d\leq x}\log^2\frac{x}{d}\right)\\ &\,\,\color{blue}{=x\sum_{d\leq x}\frac{\mu(d)}{d}\log^2\frac{x}{d}+\mathcal{O}(x)} \end{align*}

other way: On the other hand he derives in (2.5) \begin{align*} \color{blue}{\sum_{n\leq x}}&\color{blue}{\theta_n}=\log^2 x+\sum_{p^{\alpha}\leq x}\log p\log \frac{x^2}{p} +2\sum_{{p^{\alpha}q^{\beta}\leq x}\atop {p1}}\log^2 x\right) +\mathcal{O}\left(\sum_{{p^{\alpha}q^{\beta}\leq x}\atop{\alpha >1}}\log p \log q\right)+\log^2 x\\ &\,\,\color{blue}{=\sum_{p\leq x}\log^2 p+\sum_{pq\leq x}\log p\log q+\mathcal{O}(x)} \end{align*}

Equating these two derivations from $$\sum_{n\leq x}\theta_n$$ results in Selberg's symmetry formula (2.6) and its validity is shown in the paper in the following sections.

Conclusion: I think finding these two different derivations of $$\sum_{n\leq x}\theta_n$$ and equating them is related to finding the number of elements of a set by a bijection in two different ways. Furthermore we have plain counting arguments when looking at the index regions of the sums, besides the usage of elementary analytical properties of the logarithms. So, this can be seen as application of combinatorial techniques.

• @Andrew: Many thanks for granting the bounty. :-) Btw. I've already upvoted your question some days ago, since it inspired me to look somewhat closer at Selberg's very nice symmetry formula. – Markus Scheuer Oct 18 '20 at 18:58