Elementary and combinatorial methods for counting prime numbers

Although prime numbers are elementary objects in number theory, the first non-trivial results about their distribution in history rely on analytical methods (see [10]). It was a big surprise when Erd?s [5] and Selberg [12] discovered new proofs of the celebrated prime number theorem without the help of advanced tools from (complex) analysis. However, both approaches, which are not completely unrelated (see [8]), still make use of limits, in particular the real logarithm. In this article we shall introduce a rational logarithm without using any limit, and then derive classical results first due to Euler, Chebyshev and Mertens. Moreover, we revisit all necessary elementary results about prime numbers, sometimes proven in a more combinatorial fashion than usual.     

A combinatorial identity involving relatively prime integers

In this note we establish an identity concerning the number of ways an element in the semigroup generated by two relatively prime integers can be written in terms of the other elements of the semigroup.     

On a class of relatively prime sequences

For each natural number n, let a₀(n) = n, and if a₀(n),…,a_i(n) have already been defined, let a_i+1(n) > a_i(n) be minimal with (a_i+1(n), a₀(n) … a_i(n)) = 1. Let g(n) be the largest a_i(n) not a prime or the square of a prime. We show that g(n) ～ n and that $\text{g(n) > n + cn}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log}\text{(n)}$ for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” a_i(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime $\text{p < n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ with [$\text{n}\text{p}$] composite.     

Cycles of relatively prime length and the road coloring problem

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive integerk and for any aperiodic and strongly connected graphG with all vertices of out-degreek, we can labelG with symbols in an alphabet ofk letters so that all the edges going out from a vertex take a different label and all paths inG presenting a wordW terminate at the same vertex, for someW. Such a labelling is calledsynchronizing coloring ofG. Anyaperiodic graphG contains a setS of cycles where the greatest common divisor of the lengths equals 1. We establish some geometrical conditions onS to ensure the existence of a synchronizing coloring.     

Partition into terms with prime numbers

The survey covers works on the additive number theory during the period 1954–1977. Results pertaining to the classical problems of Goldbach, Hardy-Littlewood, and analogous problems are considered.Translated from Itogi Nauki i Tekhniki, Algebra, Topologiya, Geometriya, Vol. 16, pp. 5–33, 1978.     

Class numbers with many prime factors

Here, we construct infinitely many number fields of any given degree d>1 whose class numbers have many prime factors.     

The Noether numbers for cyclic groups of prime order

The Noether number of a representation is the largest degree of an element in a minimal homogeneous generating set for the corresponding ring of invariants. We compute the Noether number for an arbitrary representation of a cyclic group of prime order, and as a consequence prove the “2p−3 conjecture.”     

Exceptional characters and prime numbers in short intervals

Under the assumption of the Riemann hypothesis the asymptotic value y/log x is known to hold for the number of primes in the short interval [x - y, x] for for every fixed . We show under the assumption of the existence of exceptional Dirichlet characters the same asymptotic formula holds in the shorter intervals, for some \, in wide ranges of x depending on the characters.     

Prime and prime power divisibility of Catalan numbers

For any prime p, the sequence of Catalan numbers

$\text{a}{}_{\mathrm{n}}\text{=}\text{1}\text{n}\text{2n?2}\text{n?1}$

is divided by the a_n prime to p into blocks B_k(k > 0) of a_n divisible by p. The lengths and positions of the B_k are determined. Additional results are obtained on prime power divisibility of Catalan numbers.     

Quadratic residues and the distribution of prime numbers

D. Shanks [11] has given a heuristical argument for the fact that there are “more” primes in the non-quadratic residue classes modq than in the quadratic ones. In this paper we confirmShanks' conjecture in all casesq<25 in the following sense. Ifl ₁ is a quadratic residue,l ₂ a non-residue modq, ε(n, q, l ₁,l ₂) takes the values +1 or ?1 according ton?l ₁ orl ₂ modq, then $$\mathop {\lim }\limits_{x \to \infty } \sum\limits_p {\varepsilon (p,q,l_1 ,l_2 )} \log pp^{ - \alpha } \exp ( - (\log p)^2 /x) = - \infty$$ for 0≤α<1/2. In the general case the same holds, if all zeros ?=β+yγ of allL(s, χ modq),q fix, satisfy the inequality β²?γ²<1/4.     

On a Diophantine inequality involving prime numbers

The Ramanujan Journal - Let $$2&lt; c &lt; \frac{52}{25}$$. In this paper, it is proved that for any sufficiently large real number N, the Diophantine inequality $$|p_1^{c} + p_2^{c} +...     

Pointwise ergodic theorem along the prime numbers

The pointwise ergodic theorem is proved for prime powers for functions inL ^p,p>1. This extends a result of Bourgain where he proved a similar theorem forp>(1+√3)/2. This paper is a part of the author’s Ph.D. thesis supervised by V. Bergelson.