Combinatorial Technique in Selberg's Symmetry Formula

Question

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.

Supplementary Question (If possible Please Answer, but not mandatory for Bounty):

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)$?

Answer 1

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 {p<q}}\log p\log q\\ &=\sum_{p\leq x}\log^2 p+\sum_{pq\leq x}\log p\log q+\mathcal{O}\left(\sum_{p\leq x}\log p\log \frac{x}{p}\right)\\ &\qquad+\mathcal{O}\left(\sum_{{p^{\alpha}\leq x}\atop{\alpha>1}}\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.