Journal de Théorie des Nombres de Bordeaux

David Adam

Optimalité pour un problème de Bézivin

Brigitte Adam

Georges Rhin

Brigitte ADAM et Georges RHIN
Periodic Jacobi–Perron expansions associated with a unit II
Tome 31, no 3 (2019), p. 603-611.
<http://jtnb.centre-mersenne.org/item?id=JTNB_2019__31_3_603_0>
© Société Arithmétique de Bordeaux, 2019, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.centre-mersenne.org/), implique
l’accord avec les conditions générales d’utilisation (http://jtnb.
centre-mersenne.org/legal/). Toute reproduction en tout ou partie
de cet article sous quelque forme que ce soit pour tout usage autre
que l’utilisation à fin strictement personnelle du copiste est con-
stitutive d’une infraction pénale. Toute copie ou impression de ce
fichier doit contenir la présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.centre-mersenne.org/
Journal de Théorie des Nombres
de Bordeaux 31 (2019), 603–611
Periodic Jacobi–Perron expansions associated
with a unit II
par Brigitte ADAM et Georges RHIN
Résumé. Pour toute unité d’un corps de nombres réel K de degré n + 1,
il n’existe qu’un nombre fini de n-uples dans Kn qui ont un développement
purement périodique par l’algorithme de Jacobi–Perron associé à cette unité.
Nous donnons un algorithme explicite pour calculer tous ces n-uples pour tous
les degrés n+ 1 et toutes les unités de K.
Abstract. For any unit ε in a real number field K of degree n + 1, there
exist only a finite number of n-tuples in Kn which have a purely periodic
expansion by the Jacobi–Perron algorithm associated with this unit. We give
an explicit algorithm to compute all these n-tuples for any degree n+ 1 and
any unit of K.
1. Introduction
One of the generalizations of the continued fraction algorithm to higher
dimensions is the Jacobi–Perron Algorithm (JPA). Its main interest lies
in the great simplicity of its definition. For n = 1, we get the continued
fraction algorithm.
The continued fraction expansion of a real number α is ultimately pe-
riodic if and only if α is a real quadratic number. Moreover, a quadratic
number α has a purely periodic expansion if and only if α > 1 and its
conjugate α satisfies −1 < α < 0 (we say that α is reduced) [3, p. 50].
In this case, if l denotes a period length and
(pi
qi
)
(i ≥ 0) the sequence of
convergents of α then we have:
(1.1)
(
pl pl−1
ql ql−1
)(
α
1
)
= ε
(
α
1
)
,
where ε = qlα+ ql−1 is a unit of Q(α).
Proof. The characteristic polynomial of the 2 × 2 matrix on the left-hand
side of (1.1) is equal to x2 − x (pl + ql−1) + plql−1 − qlpl−1. P has a root
ε > 1 which is a unit since P (0) = ±1. Then, since the expansion of α is
Manuscrit reçu le 7 juin 2018, révisé le 26 juin 2019, accepté le 9 octobre 2019.
2010 Mathematics Subject Classification. 11Y40, 11Y16.
Mots-clefs. Jacobi–Perron algorithm, units.
604 Brigitte Adam, Georges Rhin
purely periodic with a period of length l, we have α = plα+pl−1qlα+ql−1 , it is easy
to verify that ε = qlα+ ql−1. 
This property is also valid for purely periodic JPA expansions with n >
1. It is called the Hasse–Bernstein Theorem [5] and ε is called a Hasse–
Bernstein unit. E. Dubois, A. Fahrane and R. Paysant-Le Roux [6] proved
that, for n = 2, deg(K) = 3, the Hasse–Bernstein units are always Pisot
numbers and that this is not always true for n ≥ 3.
Several authors have presented a few classes of periodic JPA expansions:
see [7], [8]. In [9] C. Levesque and G. Rhin presented new periodic expan-
sions in cubic number fields depending on parameters. The length of the
period tends to infinity with the parameters. B. Adam [1] generalized [9]
and P. Voutier [11] gave new periodic expansions in number fields depend-
ing on parameters.
For n = 1, it is well-known that if ε is a unit of a real quadratic field
K, then there exists only a finite number of reduced elements in K whose
continued fraction expansion is associated with ε by (1.1).
In [2] B. Adam and G. Rhin generalised this result as follows. Let K be
a real number field of degree n + 1 and ε a unit of K, there exist only a
finite number of elements in Kn whose JPA expansion is purely periodic
and associated with ε (as defined in Definition 4).
Moreover in the same paper, for n = 2, B. Adam and G. Rhin [2] gave
an explicit algorithm which gives, for any unit, all the purely periodic ex-
pansions associated with this unit.
Here we give an explicit algorithm to compute all these expansions for
any real number field K and any unit in K.
In Section 2, we recall the basic facts that are needed in the other parts of
the paper. In Section 3, we give our algorithm and in Section 4, we provide
some information about the application of this algorithm to some specific
examples.
Acknowledgments. We thank the referee for doing an awesome job to
make this manuscript suitable for publication.
2. Preliminaries: JPA and Hasse–Bernstein theorem
We assume now that the n + 1 real numbers 1, α1, α2, . . . , αn are Q-
linearly independent.
Definition 1. Let α = (α1, α2, . . . , αn) be a vector in Rn (n ≥ 1). The
Jacobi–Perron Algorithm (JPA) expansion [10] of α is given by the two
sequences:
• (a(ν))ν≥0 in Zn where a(ν) = (a(ν)1 , a
(ν)
2 , . . . , a
(ν)
n );
• (α(ν))ν≥0 in Rn where α(ν) =
(
α
(ν)
1 , α
(ν)
2 , . . . , α
(ν)
n
)
Periodic Jacobi–Perron expansions associated with a unit II 605
defined by:
α(0) = α;
a
(ν)
i =
[
α
(ν)
i
]
for 1 ≤ i ≤ n and ν ≥ 0;
if α(ν)1 6= a
(ν)
1 , α
(ν+1)
n = 1
α
(ν)
1 −a
(ν)
1
; α(ν+1)i =
α
(ν)
i+1−a
(ν)
i+1
α
(ν)
1 −a
(ν)
1
for 1 ≤ i < n.
where [x] is the greatest integer part of x. We define a(ν)0 = 1 and α
(ν)
0 = 1
for all ν.
Definition 2. The JPA expansion of α is periodic if there exist two integers
k ≥ 0 and l > 0 such that a(k+ν)i = a
(k+ν+l)
i for all ν ≥ 0 and 0 < i ≤ n. l
is called a period length.
If k and l are the smallest integers which satisfy this equality, then k is
called the preperiod length and l is called the primitive period length. If
k = 0, then the expansion is said to be purely periodic.
Remark. If the Jacobi–Perron Algorithm (JPA) expansion [10, pp. 4–5]
of α is purely periodic, then the vectors a(ν) =
(
a
(ν)
1 , a
(ν)
2 , . . . , a
(ν)
n
)
in Zn
satisfy the following Perron Conditions P1:
for ν ≥ 0 and 0 ≤ i ≤ n,(
a
(ν)
n , a
(ν+1)
n−1 , . . . , a
(ν+i)
n−i
)
≥
(
a
(ν)
i , a
(ν+1)
i−1 , . . . , a
(ν+i−1)
1 , a
(ν+i)
0
)
in lexicographical order.
Definition 3. We define the sequence A(ν) =
(
A
(ν)
0 , A
(ν)
1 , A
(ν)
2 , . . . , A
(ν)
n
)
of vectors in Zn by:
for 0 ≤ i ≤ n and 0 ≤ j ≤ n, A(j)i =
{
1 if i = j
0 otherwise
for ν ≥ 0 and 0 ≤ i ≤ n,
A
(ν+n+1)
i = A
(ν)
i + a
(ν)
1 A
(ν+1)
i + · · ·+ a
(ν)
n A
(ν+n)
i .
We have the following formulas, which were shown by Perron [10]:
• αi =
∑n
j=0A
(ν+j)
i α
(ν)
j∑n
j=0A
(ν+j)
0 α
(ν)
j
for all ν ≥ 0 and 1 ≤ i ≤ n,
• by writing
(2.1) Aν =

a
(ν)
n 1 0 . . . 0
a
(ν)
n−1 0
. . . . . . ...
...
... . . . . . . 0
a
(ν)
1 0 . . . 0 1
1 0 . . . . . . 0

,
606 Brigitte Adam, Georges Rhin
we have
A(ν) = A0A1 · · · Aν−1 =

A
(ν+n)
n . . . . . . A
(ν)
n
... . . . . . .
...
... . . . . . .
...
A
(ν+n)
0 . . . . . . A
(ν)
0
 .
Definition 4. If the JPA expansion of α = (α1, α2, . . . , αn) is purely peri-
odic with a period length l, then
ε = A(l)0 + α1A
(l+1)
0 + · · ·+ αnA
(l+n)
0 =
l−1∏
ν=0
α(ν)n .
is a unit of K = Q (α1, . . . , αn). If l is the primitive period length, this is
the Hasse–Bernstein unit [4, Theorem 17, p. 109] and we say that this JPA
expansion is associated with the unit ε.
We have
A(l)

αn
...
α1
1
 = ε

αn
...
α1
1
 .
Notice that this is a higher dimensional version of the 2-dimensional
relationship in (1.1).
Definition 5. We say that a matrix A is a JPA matrix of length l > 0 if
there is a finite sequence of integers (a(ν)i ), 0 ≤ ν ≤ l − 1, 0 < i ≤ n such
that A = A0A1 · · · Al−1 where the matrices Ai are defined by (2.1) and the
integers a(ν)i satisfy the Perron conditions P1. We say that each Ai is an
elementary JPA matrix.
Definition 6. We say that a matrix A is a JPA period matrix if A is a
JPA matrix of length l > 0 and if the infinite sequence of integers (a(j)i ),
j ≥ 0, 0 < i ≤ n defined by a(kl+ν)i = a
(ν)
i , for 0 ≤ ν ≤ l− 1, 0 < i ≤ n and
k ≥ 1 satisfies the Perron conditions P1.
Observe that for any elementary JPA matrixA, the first column ofA, say
(an, . . . , a1, 1)T , satisfies the Perron conditions P1, so we have an ≥ ai ≥ 0
for all 1 ≤ i ≤ n− 1 and an ≥ 1.
Periodic Jacobi–Perron expansions associated with a unit II 607
The following theorem has been proved in [2] as Theorem 3.1.
Theorem 7. Let K be a real number field of degree n + 1 and ε > 1 a
unit of K. There exist only a finite number of elements in Kn whose JPA
expansion is purely periodic associated with ε.
We search for a vector α = (α1, α2, . . . , αn) in Kn such that the JPA
expansion of α is purely periodic and associated with ε, that is to say we
search for the JPA period matrices A such that
A

αn
...
α1
1
 = ε

αn
...
α1
1
 .
With the previous notations we have the following lemma.
Lemma 8. Suppose that A is a JPA matrix of length k, where k is an
integer satisfying 1 ≤ k ≤ n+ 1. The first k columns of A, denoted here as
A1, . . . ,Ak, each satisfy the property P2: A1j ≥ An+1j ≥ 1, and A1j ≥ Aij ≥ 0
for 2 ≤ i ≤ n. Denote by Ej the j-th column of the (n + 1) × (n + 1)
identity matrix. Then, the last n+ 1−k columns of A are equal to Ej−k for
k + 1 ≤ j ≤ n+ 1.
Proof. The proof follows by induction on k.
The lemma is true for k = 1 because, in this case, A is an elementary
JPA matrix which satisfies P1.
For a fixed k ≥ 1 denote by B the next elementary JPA matrix and
C = AB. The first column of B is (bn, . . . , b1, 1)T and it satisfies the property
P2. So the first column of C is equal to
C1 = bnA1 + · · ·+ bn+1−kAk + bn−kE1 + · · ·+ b1En−k + En+1−k
and the next n columns are A1, . . . ,Ak, E1, . . . , En−k. Since bn ≥ 1 and all
other bj are non-negative, it is clear that for each row the i-th term of C1 is
greater or equal to the i-th term of A1 and, since the columns A1, . . . ,Ak
satisfy the property P2. This proves the lemma. 
3. The Algorithm
Let K be a real field of degree n + 1 ≥ 2 and ε > 1 a unit such that
K = Q(ε) with Q as its minimal polynomials over Z. Let A be any JPA
period matrix associated with ε, then Q(A) = 0.
3.1. Construction of JPA period matrices. We can write any peri-
odic JPA matrix as A = A0A1 · · · Al−1 for some l ≥ 1 and build A by
constructing each of the Ak’s inductively for k = 0, . . . , l − 1.
608 Brigitte Adam, Georges Rhin
Initial step. By Lemma 8, the first column V = (vn+1, . . . , v1)T of any
periodic JPA matrix A satisfies the property P2. So vn+1 ≥ vi ≥ 0 for
all 2 ≤ i ≤ n + 1 and vn+1 ≥ v1 ≥ 1. Moreover, as a consequence of
P2, in particular that all the elements of A are non-negative, we find that
vn+1 ≤ trace(A) = trace(Q), the equality holding becauseQ(A) = 0 implies
trace(A) = trace(Q).
For all such column vectors, V , we proceed to the inductive step with
k = 0.
Inductive step. For a given k ≥ 0, we suppose we have the first column
of a JPA matrix Ak · · · Al−1 and we will determine both Ak and the first
column of Ak+1 · · · Al−1.
We use V = (vn+1, . . . , v1)T to denote the first column of Ak · · · Al−1
and W to denote the first column of Ak+1 · · · Al−1. From Lemma 8, there
are two possibilities.
(a) We may have W = E1. In this case, the first column of Ak is V and
Ak+1 · · · Al−1 is the (n+ 1)× (n+ 1) identity matrix. So A = A0 · · · Ak.
We now check whether Q(A) = 0. If so, then we report A as a periodic
JPA matrix associated with ε.
Our algorithm considers no further cases arising from such A0 · · · Ak.
(b) If W 6= E1, then we let (an, . . . , a1, 1)T be the first column of Ak. So
W = A−1k V and since
A−1k =

0 0 . . . . . . 0 1
1 0 . . . . . . 0 −an
0 1 . . . . . . 0 −an−1
0 . . . . . . . . . . . .
...
0 . . . . . . 0 1 −a1
 ,
we haveW = (v1, vn+1 − anv1, vn − an−1v1, . . . , v2 − a1v1)T . We let the ai’s
range over all possibilities such that the Perron conditions P1 are satisfied
for ν = 0, . . . , k and so that the elements of W are all non-negative. To
reduce the number of possibilities even further, we also check that the
elements of W satisfy Lemma 8 (to make the program run in a feasible
amount of time, such constraints on the ai’s should be applied as early
as possible). In this way, we get a collection of all possible Ak’s and their
associated W ’s.
We now apply the inductive step for each such W .
Note that this algorithm does terminate as at every inductive step, we
find that the sum of the elements of Ak+1 · · · Al−1 is smaller than the sum
of the elements of Ak · · · Al−1 (due to the nature of A−1k ) and these elements
are all non-negative integers. Hence after finitely many steps, it must stop.
Periodic Jacobi–Perron expansions associated with a unit II 609
3.2. Computation of α1, . . . , αn in Q(ε). From the steps in Subsec-
tion 3.1, we have now determined all the JPA period matrices, A, associated
to ε. We now show how to use our knowledge of A and ε to calculate the
αi’s exactly. Note that this is the problem of finding the eigenvectors of A
that are associated with ε.
For 1 ≤ i ≤ n, we write the αi’s as
αi =
(n+1)i∑
j=(n+1)(i−1)+1
cjε
j−((n+1)(i−1)+1),
where the cj ’s are rational numbers.
We have the equation:
A

αn
...
α1
1
 = ε

αn
...
α1
1
 .
We subtract the right-hand term side from the left-hand side and reduce
each component of this vector modulo Q(ε). Then, each component, which
is a polynomial in ε of degree at most n, has all its coefficients equal to
0. This gives a linear system Ec = S of (n + 1)2 equations and n2 + n
unknowns c = (c1, . . . , cn2+n). Keeping the first n2 + n equations of this
linear system, we get Fc = T . Thus c = F−1T .
4. Numerical computations
4.1. The units are Pisot numbers. Here we give some examples for
the degrees 4, 5 and 6 when the units are Pisot numbers. The periods
will not be always primitive. The programs have been written in Pascal. A
compiled language like Pascal was used, rather than interpreted languages
like Maple or Pari, due to speed, as the computations for each example do
take a substantial amount of time.
[K : Q] = 4, n = 3.
Let Q1 = x4−430x3 +291x2−46x+1. All its roots are real and only one is
greater than 1, ε = 429.322437 . . .. Note that ε = ω4 where ω is the unique
root of R1 = x4− 4x3− 3x2 + 2x+ 1 that is real and greater than 1. There
are 666 matrices giving purely periodic JPA developments associated to ε,
596 with period of length 4, 42 of length 6, 8 of length 8 and 20 of length 10.
[K : Q] = 5, n = 4.
Let Q2 = x5 − 57x4 − 42x3 − 22x2 − 7x − 1. It has ε = 57.734109 . . . as a
root. Note that ε = ω5 where ω = 1.965948 . . . is a root of the polynomial
R2 = x5−x4−x3−x2−x−1. There are 576 matrices giving purely periodic
JPA developments associated to ε, 1 with period of length 1, 19 with period
610 Brigitte Adam, Georges Rhin
of length 2, 43 with period of length 3, 498 with period of length 4, 1 with
period of length 6 (its primitive period is of length 1) and 14 with period
of length 7.
[K : Q] = 6, n = 5.
Let Q3 = x6−63x5+129x4−111x3+49x2−11x+1. It has ε = 60.911887 . . .
as a root. Here ε = ω6, where ω = 1.983582 . . . is a root of the polynomial
R3 = x6− x5− x4− x3− x2− x− 1. There are 2858 matrices associated to
ε, all with period of length 6.
4.2. The units are not Pisot numbers. Here we use examples obtained
from the example given on p. 275 of [6], with a3 = a4 = a1 = 3 and a2 = 0.
[K : Q] = 5, n = 4.
Let R4 = x5 − 3x4 − 3x3 − 3x − 1. ω = 3.8390646 . . . is a root of R4. It
is not a Pisot number since it has a real conjugate less than −1. For each
k = 1, . . . , 4, there is only one matrix which is associated to ωk. Note that
the maximum of trace
(
ωk
)
occurs for k = 4 and is 219.
References
[1] B. Adam, “Families of periodic Jacobi-Perron algorithms in any dimension with period
lengths going to infinity”, Acta Arith. 177 (2017), p. 293-299.
[2] B. Adam & G. Rhin, “Periodic Jacobi-Perron expansions associated with a unit”, J. Théor.
Nombres Bordeaux 23 (2011), no. 3, p. 527-539.
[3] A. Baker, A concise introduction to the theory of numbers, Cambridge University Press,
1984.
[4] L. Bernstein, The Jacobi–Perron Algorithm, Its Theory and Applications, Lecture Notes
in Mathematics, vol. 207, Springer, 1971.
[5] L. Bernstein & H. Hasse, “Einheitenberechnung mittels des Jacobi–Perronschen Algorith-
mus”, J. Reine Angew. Math. 218 (1965), p. 51-69.
[6] E. Dubois, A. Farhane & R. Paysant-Le Roux, “The Jacobi-Perron algorithm and Pisot
numbers”, Acta Arith. 111 (2004), no. 3, p. 269-275.
[7] E. Dubois & R. Paysant-Le Roux, “Développements périodiques par l’Algorithme de
Jacobi–Perron et nombre de Pisot–Vijayaraghavan”, C. R. Math. Acad. Sci. Paris 272
(1971), p. 649-652.
[8] ———, “Une application des nombres de Pisot à l’algorithme de Jacobi–Perron”, Monatsh.
Math. 98 (1984), p. 145-155.
[9] C. Levesque & G. Rhin, “Two families of periodic Jacobi–Perron algorithms with period
lengths going to infinity”, J. Number Theory 37 (1991), no. 2, p. 173-180.
[10] O. Perron, “Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus”, Math.
Ann. 64 (1907), p. 1-76.
[11] P. Voutier, “Families of Periodic Jacobi–Perron Algorithms for all Period Lengths”, J.
Number Theory 168 (2016), p. 472-486.
Periodic Jacobi–Perron expansions associated with a unit II 611
Brigitte Adam
2, clos du pré,
57530 Courcelles-Chaussy, France
E-mail: brigitte.anne.adam@gmail.com
Georges Rhin
UMR CNRS 7502, IECL, Université de Lorraine, site de Metz,
Département de Mathématiques, UFR MIM
3 rue Augustin Fresnel
BP 45112
57073 Metz cedex 03, France
E-mail: georges.rhin@univ-lorraine.fr
URL: http://www.iecl.univ-lorraine.fr/~Georges.Rhin/


Periodic Jacobi–Perron expansions associated with a unit II

Alisa Sedunova

A logarithmic improvement in the Bombieri–Vinogradov theorem

Félicien Comtat

A uniform estimate for the density of rational points on quadrics

Raphael S. Steiner

Raphael S. STEINER
Near Counterexamples to Weil’s Converse Theorem
Tome 31, no 2 (2019), p. 313-321.
<http://jtnb.centre-mersenne.org/item?id=JTNB_2019__31_2_313_0>
© Société Arithmétique de Bordeaux, 2019, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.centre-mersenne.org/), implique
l’accord avec les conditions générales d’utilisation (http://jtnb.
centre-mersenne.org/legal/). Toute reproduction en tout ou partie
de cet article sous quelque forme que ce soit pour tout usage autre
que l’utilisation à fin strictement personnelle du copiste est con-
stitutive d’une infraction pénale. Toute copie ou impression de ce
fichier doit contenir la présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.centre-mersenne.org/
Journal de Théorie des Nombres
de Bordeaux 31 (2019), 313–321
Near Counterexamples to Weil’s Converse
Theorem
par Raphael S. STEINER
Résumé. Nous démontrons que dans le théorème réciproque de Weil les équa-
tions fonctionnelles pour les caractères de Dirichlet modulo ≤
√
p−24
3 ne suf-
fisent pas à assurer la modularité relativement au groupe Γ0(p), où p est un
nombre premier.
Abstract. We show that in Weil’s converse theorem the functional equations
of multiplicative twists of the first
√
p−24
3 moduli are not sufficient to conclude
modularity for the group Γ0(p), where p is a prime number.
1. Introduction
Let SL2(R) act on the upper half-plane H by Möbius transformations.
That is, we define as usual
γz = az + b
cz + d for γ =
(
a b
c d
)
∈ SL2(R).
For such a matrix, we further define the cocycle j(γ, z) = cz + d and an
action on the holomorphic functions f : H→ C on the upper half-plane as
(f |kγ)(z) = j(γ, z)−kf(γz). For our convenience, let us denote the following
special matrices:
S =
(
0 −1
1 0
)
, T =
(
1 1
0 1
)
, WN =
(
0 −N−
1
2
N
1
2 0
)
.
Let (am)m∈N, (bm)m∈N be two complex sequences that satisfy |am|, |bm| =
O(mσ) for some σ > 0, where we follow Landau’s big O convention. Asso-
ciated to these sequences, we define the two holomorphic functions on the
upper half-plane:
f(z) =
∑
m≥1
ame(mz) and g(z) =
∑
m≥1
bme(mz),
Manuscrit reçu le 25 septembre 2017, accepté le 11 mai 2019.
2010 Mathematics Subject Classification. 11F66, 11F11.
Mots-clefs. Converse Theorem, Modular Forms, Multiplier System.
314 Raphael S. Steiner
where e(z) = e2πiz. Let us further define their associated Dirichlet series
and completions thereof:
L(f, s) =
∑
m≥1
amm
−s, L(g, s) =
∑
m≥1
bmm
−s,
Λ(f, s) = (2π)−sΓ(s)L(f, s), Λ(g, s) = (2π)−sΓ(s)L(g, s),
where Γ(s) is the Euler gamma function. These are a priori only defined for
<(s) > σ + 1. For k ∈ Z, Hecke [2] proved the equivalence of the following
two statements.
(1) f, g are cusp forms of weight k for SL2(Z), and (f |kS)(z) = g(z).
(2) The functions Λ(f, s) and Λ(g, s) admit a holomorphic continuation
to the whole complex plane, are bounded in any vertical strip, and
satisfy the functional equation
Λ(f, s) = ikΛ(g, k − s).
An equivalent statement for
Γ0(N) =
{(
a b
c d
)
∈ SL2(Z)
∣∣∣∣N |c}
is much harder. Especially, the implication going from the functional equa-
tions to proving that f and g must be cusp forms requires further informa-
tion. Weil [7] resolved this issue by assuming additional functional equations
coming from multiplicative twists. To this end, define for a primitive char-
acter ψ modulo q with (q,N) = 1 the Dirichlet series and their respective
completions
L(f, ψ, s) =
∑
m≥1
amψ(m)m−s, L(g, ψ, s) =
∑
m≥1
bmψ(m)m−s,
Λ(f, ψ, s) = (2π)−sΓ(s)L(f, ψ, s), Λ(g, ψ, s) = (2π)−sΓ(s)L(g, ψ, s).
Let M be a fixed positive integer. Assume for every primitive character
ψ modulo q with (q,MN) = 1 the holomorphic continuation of Λ(f, ψ, s),
Λ(g, ψ, s) to the whole complex plane and boundedness in any vertical strip.
Furthermore, assume all the functional equations
Λ(f, ψ, s) = ikχ(q)ψ(N)τ(ψ)
2
q
(Nq2)
k
2−sΛ(g, ψ, k − s),
for some fixed Dirichlet character χ of modulus N , where τ(ψ) is the Gauss
sum of ψ. In this case, Weil [7] was able to prove that f , respectively g,
are cusp forms of weight k for Γ0(N) with Nebencharakter χ, respectively
χ, and (f |kWN )(z) = g(z). Khoai [3] later refined the number of func-
tional equations of twists required. He proved that the primitive twists ψ
of modulus q < N2 with (q,N) = 1 suffice to come to the same conclusion.
Moreover, if N = pr is a power of a prime, then already q < N suffices. In
Near Counterexamples to Weil’s Converse Theorem 315
this paper, we are able to show that for N = p, a prime, it is not sufficient to
only assume the functional equations of the primitive multiplicative twists
of modulus at most ( 1√3 + o(1))
√
p.
Theorem 1.1. Let p ≥ 29 be a prime, χ an even Dirichlet character
modulo p and k ≥ 16 an even integer. There exist two complex sequences
(am)m∈N, (bm)m∈N with |am|, |bm| = O(mσ) for some σ > 0 which satisfy
the following two properties:
(1) Both f(z) =
∑
m≥1 ame(mz) and g(z) =
∑
m≥1 bme(mz) are not
elements of
⋃
l,N Sl(Γ(N)), that is to say f and g are not classical
cusp forms of any weight for any congruence subgroup.
(2) For any primitive character ψ modulo q with (q, p) = 1, the func-
tions Λ(f, ψ, s),Λ(g, ψ, s) can be holomorphically continued to the
whole complex plane, are bounded in any vertical strip. If q ≤√
p−24
3 , they furthermore satisfy the functional equation
(1.1) Λ(f, ψ, s) = ikχ(q)ψ(p)τ(ψ)
2
q
(pq2)
k
2−sΛ(g, ψ, k − s).
In the context of converse theorems for classical modular forms, it is
more natural to look at additive twists rather than multiplicative ones. For
this purpose, we define for (a, q) = 1:
L
(
f, aq , s
)
=
∑
m≥1
ame
(
am
q
)
m−s, L
(
g, aq , s
)
=
∑
m≥1
bme
(
am
q
)
m−s,
Λ
(
f, aq , s
)
= (2π)−sΓ(s)L
(
f, aq , s
)
, Λ
(
g, aq , s
)
= (2π)−sΓ(s)L
(
g, aq , s
)
.
For additive twists, we are able to give the following converse theorem for
prime level p.
Theorem 1.2. Let p > 3 be a prime. There exists a (computable) set Q of
2b p12c+3 natural numbers q, which satisfy 1 ≤ q ≤ p−2, such that for every
integer k > 0 and Dirichlet character χ modulo p with χ(−1) = (−1)k the
following holds. Given any two complex sequences (am)m∈N and (bm)m∈N
with |am|, |bm| = O(mσ) for some σ > 0, then the following two statements
are equivalent:
(1) f(z) =
∑
m≥1 ame(mz) is a cusp form of weight k for Γ0(p) with
Nebencharakter χ and (f |kWp)(z) = g(z) =
∑
m≥1 bme(mz).
(2) For every q ∈ Q, the functions Λ(f, −1q , s) and Λ(g,
(qq?+1)/p
q , s),
where 1 ≤ q? ≤ p and satisfies qq? ≡ −1 mod(p), can be holomor-
phically continued to the whole complex plane and are bounded in
every vertical strip, and satisfy the functional equation
(1.2) Λ
(
f,
−1
q
, s
)
= ikχ(q)(pq2)
k
2−sΛ
(
g,
(qq? + 1)/p
q
, k − s
)
.
316 Raphael S. Steiner
Remark 1.3. The number of functional equations of additive twists to go
back from (2) to (1) in Theorem 1.2 is essentially optimal as one can con-
struct counterexamples similar to the proof of Theorem 1.1 if one assumes
at most 2b p12c − 2 additive twists.
Note that this further strengthens Khoai’s result, since, by using Gauss
sums, one may reduce down to about p/6 moduli for which one needs to
consider the multiplicative twists.
The proofs of both theorems rely on Hecke’s converse theorem [2], which
in its most general form, proven by Bochner [1], establishes an equivalence of
a functional equation and a modular relation. Subsequently, Theorem 1.2
follows from a result of Rademacher [5] on the generators of Γ0(p). The
proof of Theorem 1.1, however, relies on the interesting observation that
the modularity of |f | for a finite index subgroup Γ ⊆ SL2(Z), i.e. |(f |kγ)| =
|f |,∀ γ ∈ Γ, does not always imply the modularity (in the classical sense)
of f on some congruence subgroup Γ(N), despite this being the case for the
full modular group Γ = SL2(Z), where it would follow that f is modular
on Γ(12). Essentially, this was shown by van Lint [4] as a consequence of
the fact that Γ(12) is contained in the commutator subgroup of SL2(Z). In
general, it is no longer true that the commutator subgroup of a finite index
subgroup Γ of SL2(Z) is a congruence subgroup. In fact, the abelianisation
of the group Γ0(p) has rank approximately p/6 (see Corollary 2.2). It is this
large rank which will give us plenty of freedom to construct a multiplier
system υ of infinite order satisfying certain equations stemming from the
imposed functional equations of multiplicative twists. Such a multiplier
system is of course never trivial on any congruence subgroup and therefore
cannot agree with a multiplier system that comes from a Dirichlet character.
Hence, any non-trivial cusp form with respect to the constructed multiplier
system υ gives rise to the counterexample in Theorem 1.1.
2. Notation and Preliminaries
Let Γ be a finite index subgroup of SL2(Z) that contains −I. We call a
group character υ : Γ→ S1 that satisfies υ(−I) = (−1)k amultiplier system
of weight k for Γ. We call a holomorphic function f on the upper half-plane
modular of weight k for Γ with respect to υ if it satisfies (f |kγ)(z) =
υ(γ)f(z) for every γ ∈ Γ. Such a function f admits an expansion of the
shape
(f |kτ)(z) =
∞∑
m=−∞
ame
(
m+ κτ
nτ
z
)
for every τ ∈ SL2(Z), where nτ is the cusp width of the cusp τ∞ and
κτ is the cusp parameter at the cusp τ∞. They are both independent of
the choice of representative of τ∞ mod(Γ). The former is characterised by
Near Counterexamples to Weil’s Converse Theorem 317
being the smallest natural number n such that τTnτ−1 ∈ Γ and the latter is
characterised by e(κτ ) = υ(τTnτ τ−1) and κτ ∈ [0, 1). We say f is a modular
form of weight k for Γ with respect to υ if we can restrict the summation
to m + κτ ≥ 0 for every τ ∈ SL2(Z). Moreover, we say f is a cusp form
of weight k for Γ with respect to υ if the summation can be restricted to
m+κτ > 0 for every τ ∈ SL2(Z). We refer the interested reader to [6] for a
more detailed treatment on modular forms (of arbitrary real weight) with
respect to an arbitrary multiplier system.
Let Γ = Γ0(p), where p > 3 is a prime. The multiplier systems of weight
k for Γ0(p) include all Dirichlet characters χ : (Z/pZ)× → S1 with χ(−1) =
(−1)k; they are given by
υχ(γ) = χ(d) if γ =
(
a b
c d
)
∈ Γ0(p),
but, in fact, there are many more multiplier systems. They are in one-to-one
correspondence with group homomorphisms
υ : Γ0(p)
/
[Γ0(p),Γ0(p)]→ S
1
satisfying υ(−I) = (−1)k. When k is even, we can characterise this quotient
completely by a proposition of Rademacher [5].
Proposition 2.1 (Rademacher). Let p > 3 be a prime. Then, we have
Γ0(p)
/
±I
∼= Fl−2a−2b ∗ (Z/2Z ∗ Z/2Z)a ∗ (Z/3Z ∗ Z/3Z)b ,
where l = 2b p12c + 3; a = 0, unless p ≡ 1 mod(4) in which case a = 1;
b = 0, unless p ≡ 1 mod(3) in which case b = 1; and Fl−2a−2b is the free
group with l−2a−2b generators. The isomorphism stems from a set of free
generators of Γ0(p)/{±I}, which are given by S and some matrices of the
shape
Vq =
(
−q? −1
qq? + 1 q
)
,
with 2 ≤ q ≤ p − 2, where q? is the integer such that 1 ≤ q? ≤ p and
qq? ≡ −1 mod(p).
Corollary 2.2. Let p > 3 be a prime. Then, we have
Γ0(p)
/
±[Γ0(p),Γ0(p)]
∼= Zl−2a−2b × (Z/2Z)2a × (Z/3Z)2b ,
where l = 2b p12c+ 3; a = 0, unless p ≡ 1 mod(4) in which case a = 1; and
b = 0, unless p ≡ 1 mod(3) in which case b = 1.
Thus, we get plenty of freedom when p becomes large, which we may use
to satisfy certain equations.
318 Raphael S. Steiner
3. Proof of the Theorems
Let f(z) =
∑
m>0 ame(mz) be a cusp form of integer weight k > 0 with
respect to a multiplier system υ on Γ0(p) with cusp parameters κI = κS = 0
and let us denote
g(z) = (f |kWp)(z) =
∑
m>0
bme(mz),
which is another cusp form with respect to a conjugated multiplier system
of υ. Let q ∈ N with q 6= p and 0 ≤ a < q with (a, q) = 1. Let B,D be two
integers that satisfy the relation qD+apB = 1, which admits a solution by
Bézout. We have the matrix identity(
1 aq
0 1
)
=
(
D a
−pB q
)
Wp
(
p
1
2B p−
1
2 q−1
−p
1
2 q 0
)
and therefore we get the identity
(3.1)
(
f
∣∣∣∣
k
(
1 aq
0 1
))
(z) = υ
((
D a
−pB q
))(
g
∣∣∣∣
k
(
p
1
2B p−
1
2 q−1
−p
1
2 q 0
))
(z).
By definition, this is just
(3.2)
∑
m>0
ame
(
am
q
)
e(mz)
= (−1)kυ
((
D a
−pB q
))
p−
k
2 q−kz−k
∑
m>0
bme
(
−Bm
q
)
e
(
− m
pq2z
)
.
Now, f |k
( 1 a/q
0 1
)
and g|k
( 1 −B/q
0 1
)
are modular forms on Γ(pq2) for some
multiplier system, respectively. Thus, by Hecke’s original proof, Λ(f, aq , s)
and Λ(g, −Bq , s) possess a holomorphic continuation to the whole complex
plane and are bounded in every vertical strip. Furthermore, by Bochner [1,
Theorem 4], the modular relation (3.2) is equivalent to the functional equa-
tion
(3.3) Λ
(
f, aq , s
)
= ikυ
((
D a
−pB q
))
(pq2)
k
2−sΛ
(
g, −Bq , k − s
)
.
Setting υ = υχ shows the direction (1) ⇒ (2) in Theorem 1.2. For the
reverse direction, we need to fix our set Q. It shall consist of 1 and those
q for which Vq is needed to generate Γ0(p) / ± I in Proposition 2.1. We’ll
make use of the equivalence of (3.3) and (3.1), where υ
((
D a
−pB q
))
is to be
regarded as any fixed constant. First, we set (a, q,B,D) = (−1, 1,−1, 1−p)
and make use of the functional equation (1.2) for 1 ∈ Q. This yields(
f
∣∣∣∣
k
(
1 −1
0 1
))
(z) = χ(1)
(
g
∣∣∣∣
k
(
−1 −1
0 −1
)
Wp
)
(z)
Near Counterexamples to Weil’s Converse Theorem 319
or equivalently f(z) = (g|kWp)(z) and consequently (f |kWp)(z) = g(z)
after applying |kWp to both sides. With this extra information, we further
find that (3.1) is equivalent to
(
f
∣∣∣∣
k
(
D a
−pB q
))
(z) = υ
((
D a
−pB q
))
(g|kWp) (z)
= υ
((
D a
−pB q
))
f(z).
By using this with (a, q, B,D) = (1, q,−(qq? + 1)/p,−q?), where q ∈ Q,
and the functional equation (1.2) for q, we find
(
f
∣∣∣∣
k
(
−q? 1
qq? + 1 q
))
(z) = χ(q)f(z).
By combining this with Proposition 2.1 and the trivial facts that
(f |kT )(z) = f(z) and (f |k − I)(z) = (−1)kf(z) = χ(−1)f(z), we find
that f is modular of weight k for Γ0(p) with Nebencharakter χ. The fact
that f is indeed a cusp form can be seen from the expansions at the cusps
∞ and 0 which are given by the definitions of f , respectively g.
We move onto the proof of Theorem 1.1. Let k now be even and υ, f
and g be defined as in the beginning of this section. The restriction that
κI = κS = 0 implies that the dependence on B in both
υ
((
D a
−pB q
))
and Λ
(
g, −Bq , s
)
is only on Bmod(q) (and thus only depends on q and amod q). We further
make the assumption that
(3.4) υ
((
D a
−pB q
))
= χ(q), for (a, q) = 1 and 1 ≤ q ≤ Q,
where χ is a fixed Dirichlet character modulo p. That is to say we want υ
to pretend to be the Dirichlet character χ for small values of q.
320 Raphael S. Steiner
Now, let ψ be a primitive Dirichlet character modulo q with (q, p) = 1
and 1 ≤ q ≤ Q. Then, we have
Λ(f, ψ, s) = 1
τ(ψ)
∑′
amod(q)
ψ(a)Λ
(
f, aq , s
)
= i
kχ(q)
τ(ψ)
(pq2)
k
2−s
∑′
amod(q)
ψ(a)Λ
(
g, −apq , k − s
)
= i
kχ(q)ψ(−p)
τ(ψ)
(pq2)
k
2−s
∑′
amod(q)
ψ(−ap)Λ
(
g, −apq , k − s
)
= ikχ(q)ψ(p)τ(ψ)
2
q
(pq2)
k
2−sΛ(g, ψ, k − s),
where the prime in the summation denotes that we are only summing over
(a, q) = 1 and a denotes the multiplicative inverse of amod(q). This is
the functional equation we would expect for classical modular forms with
Nebencharakter χ. In order to prove Theorem 1.1, we shall construct such
a multiplier system υ of infinite order as such a multiplier system cannot
be trivial on any congruence subgroup. We further have to show that there
is a non-zero cusp form with respect to that multiplier system for some
weight k.
Our assumptions on our multiplier system, that is (3.4) and κI = κS = 0,
form a system of linear equations with at most 2 + Q2/2 equations in
log υ(γ), where γ runs over the generators in Corollary 2.2. Moreover, this
system of equations admits a solution, namely, υχ. Thus, if 2 +Q2/2 + 5 ≤
2b p12c + 3 or Q ≤
√
(p− 24)/3 we find that the kernel has dimension at
least 5. Thus, we can find an element υ′ of infinite order in the kernel which
satisfies log υ′(γ) = 0 for any generator γ of finite order and hence υ = υ′υχ
is a multiplier system which satisfies our requirements. The construction
of a non-zero cusp form is now straightforward. As in [6, Theorem 5.1.2],
one can construct Eisenstein series for k ≥ 4, which are non-zero, say for
example GI(z; 0; Γ0(p), k, υ), and multiply it with the cusp form ∆(z) of
weight 12 for SL2(Z) to get a cusp form of weight k+ 12 with respect to υ
for Γ0(p), which concludes the proof of Theorem 1.1.
Acknowledgments. I would like to thank Andrew Booker for asking me
the question whether the modularity of |f | implies the modularity of f ,
which eventually led to the above observation, and for interesting discus-
sions as well as useful comments on earlier versions of this paper. I would
also like to thank the referee for their time and comments.
References
[1] S. Bochner, “Some properties of modular relations”, Ann. Math. 53 (1951), p. 332-363.
Near Counterexamples to Weil’s Converse Theorem 321
[2] E. Hecke, “Über die Bestimmung Dirichletscher Reihen durch ihre Funktionalgleichung”,
Math. Ann. 112 (1936), no. 1, p. 664-699.
[3] H. H. Khoai, “Sur les séries L associées aux formes modularies”, Bull. Soc. Math. Fr. 120
(1992), no. 1, p. 1-13.
[4] J. H. van Lint, “On the multiplier system of the Riemann–Dedekind function η”, Nederl.
Akad. Wet., Proc., Ser. A 61 (1958), p. 522-527.
[5] H. Rademacher, “Über die Erzeugenden von Kongruenzuntergruppen der Modulgruppe”,
Abh. Math. Semin. Univ. Hamb. 7 (1929), no. 1, p. 134-148.
[6] R. A. Rankin, Modular forms and functions, Cambridge University Press, 1977.
[7] A. Weil, “Über die Bestimmung Dirichletscher Reihen durch Funktionalgleichungen”, Math.
Ann. 168 (1967), p. 149-156.
Raphael S. Steiner
FH317
Institute for Advanced Study
1 Einstein Drive
Princeton, New Jersey 08540, USA
E-mail: raphael.steiner.academic@gmail.com
URL: http://www.math.ias.edu/~rsteiner/


Near Counterexamples to Weil’s Converse Theorem

Damien Roy

A measure of transcendence for singular points on conics

Élie Goudout

Concentrations simultanées de fonctions additives

Noam D. Elkies

Scott Duke Kominers

Configurations of Extremal Type II Codes via Harmonic Weight Enumerators

Kübra Benli

Kübra BENLİ
On the number of prime factors of the composite numbers resulting after a
change of digits of primes
Tome 31, no 3 (2019), p. 689-696.
<http://jtnb.centre-mersenne.org/item?id=JTNB_2019__31_3_689_0>
© Société Arithmétique de Bordeaux, 2019, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.centre-mersenne.org/), implique
l’accord avec les conditions générales d’utilisation (http://jtnb.
centre-mersenne.org/legal/). Toute reproduction en tout ou partie
de cet article sous quelque forme que ce soit pour tout usage autre
que l’utilisation à fin strictement personnelle du copiste est con-
stitutive d’une infraction pénale. Toute copie ou impression de ce
fichier doit contenir la présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.centre-mersenne.org/
Journal de Théorie des Nombres
de Bordeaux 31 (2019), 689–696
On the number of prime factors of the composite
numbers resulting after a change of digits of
primes
par Kübra BENLİ
Résumé. Dans cette note, nous prouvons que pour tout entier fixé K ≥ 2,
pour tout ε > 0 et pour tout x suffisamment grand, il existe au moins x1−ε
nombres premiers x < p ≤ (1 +K−1)x tels que tous les nombres entiers de la
forme pj ± ahk avec 2 ≤ a ≤ K, 0 < |k| ≤ K, 1 ≤ j ≤ K, 0 ≤ h ≤ K log x
sont des nombres composés ayant au moins (log log x)1−ε facteurs premiers
distincts.
Abstract. In this note, we prove that for any fixed integer K ≥ 2, for all
ε > 0 and for all sufficiently large x, there exist at least x1−ε primes x < p ≤
(1 + K−1)x, such that all of the integers pj ± ahk, 2 ≤ a ≤ K, 0 < |k| ≤
K, 1 ≤ j ≤ K, 0 ≤ h ≤ K log x are composite having at least (log log x)1−ε
distinct prime factors.
1. Introduction
In 1979, Erdős proved the following result, which appeared in the solution
to a problem in Mathematics Magazine [3].
Theorem 1.1 (Erdős). For all sufficiently large positive integers k, there
exist primes p,
p =
k∑
i=0
ai10i, ak > 0, 0 ≤ ai ≤ 9,
such that all of the integers p+ t 10i, 0 < |t| < 10, 0 ≤ i ≤ k are composite.
In 2011, Tao [6] proved that for any integer K ≥ 2, there exist at least
cK
x
log x primes p in the interval [x, (1 + K
−1)x] satisfying |pj ± ahk| is
composite for every 2 ≤ a ≤ K, 1 ≤ j, k ≤ K and 1 ≤ h ≤ K log x, where
cK > 0 is a constant depending only on K. In a different direction, Hao
Pan [5] proved the following theorem.
Manuscrit reçu le 11 janvier 2019, révisé le 26 mai 2019, accepté le 15 juillet 2019.
2010 Mathematics Subject Classification. 11A41, 11P32.
Mots-clefs. primes, digit, composite numbers.
Partial funding was provided by the RTG at the University of Georgia.
690 Kübra Benlı̇
Theorem 1.2. Suppose that K ≥ 2 is an integer and ε > 0 is small
number. Then for all sufficiently large (depending only on K and ε) x, there
exist at least x1−ε integers n ∈ [x, (1 + K−1)x] such that ω(nj ± ahk) ≥
(log log log x)
1
3−ε for all 2 ≤ a ≤ K, 1 ≤ j, k ≤ K and 0 ≤ h ≤ K log x.
Here, as usual, ω(m) denotes the number of distinct prime factors of m.
In [5], Pan also asked if one could improve the quoted lower bound by
a log factor. (This is a natural question as the normal order of ω(n) is
log logn.) In this note we give the affirmative answer. Indeed we prove the
following result.
Theorem 1.3. Let K ≥ 2 be an integer, ε > 0 be a small number. For
all sufficiently large positive x, there exist at least x1−ε primes x < p ≤
(1 + K−1)x, such that all of the integers pj ± ahk, 2 ≤ a ≤ K, 0 < k ≤
K, 1 ≤ j ≤ K, 0 ≤ h ≤ K log x are composite having at least (log log x)1−ε
distinct prime factors.
This result improves Theorem 1.2 in two ways; first the number of prime
factors is improved by a log factor, secondly the numbers considered are
prime numbers.
Acknowledgments. The author is grateful to the anonymous referee and
to Dr. Paul Pollack for their careful reading of the manuscript.
2. Proof of Theorem 1.3
2.1. Lemmata. We first state the results which will be used in the proof
of Theorem 1.3.
In [4], Linnik proved the following theorem.
Theorem 2.1 (Linnik’s Theorem). Let a, q be two integers such that q ≥ 1
and (a, q) = 1. There exists a prime p such that p ≡ a mod q, and p qC
for some positive absolute constant C.
Following the proof of Linnik’s Theorem in [2], one can obtain the fol-
lowing corollary. Due to lack of suitable reference we include the proof here.
Corollary 2.2. Let K > 0 be fixed. Let a, q be two integers such that q ≥ 1
and (a, q) = 1, and let x be a real number so that qc  x, for a sufficiently
large constant c > 0. Then there are at least K xq2ϕ(q) log x primes p such
that p ≡ a mod q, and x < p ≤ (1 +K−1)x.
Proof. The result in the case when q ≤ (log x)2 follows by applying the
Siegel–Walfisz Theorem. Suppose that q > (log x)2.We follow Bombieri’s
notation used in [2]. Here, L(s, χ) denotes a Dirichlet L-function for s =
σ + it, where σ and t are real numbers, and χ is a Dirichlet character
mod q. Let c1 > 0 be the constant appearing in the Landau–Page Theorem
Prime factors of the numbers resulting after a change of digits of primes 691
(see [2, p. 39]), such that L(s, χ) 6= 0 for σ ≥ 1 − c1log T , |t| ≤ T for all
primitive characters χ modm, m ≤ T except possibly for one exceptional
real character. We let χ1 denote a character modulo q, induced by an ex-
ceptional character, if it exists. In this case we let β1 denote the exceptional
zero of L(s, χ1), and we also let δ1 := 1− β1.
We put 4A := log xlog q so that (1+K
−1)x = q4c0A, where c0 = 1+ log(1+1/K)4A log q .
Then 1 < c0 < 2. Using the last equation in the proof of Linnik’s Theorem
in [2, p. 55], namely,
∑
p6x
p≡a mod q
log p = 1
ϕ(q)
(
x− χ1(a)
xβ1
β1
)
+O
(
x
ϕ(q)δ1(log q) exp (−c1A)
)
+O
(
x log x
q4
)
+O
( 1
ϕ(q)x
1/2q20
)
,
we obtain
(2.1)
∑
x<p6(1+K−1)x
p≡a mod q
log p = 1
ϕ(q)
(
K−1x− χ1(a)
((1 +K−1)β1 − 1)xβ1
β1
)
+O
(
x
ϕ(q)δ1(log q) exp
(
−c′A
))
+O
(
x log x
q4
)
+O
( 1
ϕ(q)x
1/2q20
)
.
Note that 12 < β1 < 1, so
K−1
(2+K−1) < (1 +K
−1)β1 − 1 < K−1. So we have
K−1
(2 +K−1)
xβ1
β1
<
∣∣∣∣∣χ1(a)((1 +K−1)β1 − 1)xβ1β1
∣∣∣∣∣ < K−1xβ1β1 .
If χ1(a) > 0, then
K−1x− χ1(a)
((1 +K−1)β1 − 1)xβ1
β1
> K−1x− χ1(a)K−1
xβ1
β1
.
If χ1(a) < 0, then
K−1x− χ1(a)
((1 +K−1)β1 − 1)xβ1
β1
> K−1x− K
−1
(2 +K−1)χ1(a)
xβ1
β1
>
K−1
(2 +K−1)x−
K−1
(2 +K−1)χ1(a)
xβ1
β1
.
Thus we have
K−1x− χ1(a)
((1 +K−1)β1 − 1)xβ1
β1
K x− χ1(a)
xβ1
β1
.
692 Kübra Benlı̇
For A large enough, the term x − χ1(a)x
β1
β1
is  (δ1 log q)x. So the main
term is K xϕ(q)q
−2 and the first error term on the right hand side of (2.1)
is negligible compared to the main term for large A. Moreover, it follows
from the argument given in [2] that x− χ1(a)x
β1
β1
 x
q2 . Now we note that
for A large enough, the sum of the last two error terms on the right of (2.1)
is also negligible. Thus we obtain∑
x<p6(1+K−1)x
p≡a mod q
log pK
x
ϕ(q)q
−2.(2.2)
Since each term of the sum in (2.2) is ≤ log x, the result follows. 
The following is a well known result special cases of which have been
discovered by many mathematicians independently. See [1], for example.
Theorem 2.3 (Zsigmondy’s Theorem, 1892). Let a and n be two integers
greater than 1. Then there exists a prime q such that a has order n mod q,
except exactly in the following cases:
(1) n = 2 and a = 2k − 1, where k ≥ 2.
(2) n = 6 and a = 2.
The idea Erdős used for the proof of Theorem 1.1 was to find small prime
numbers q and a prime p so that each p+t10i is divisible by one of the primes
q. In order to do that effectively (using as few small primes as possible),
he used Zsigmondy’s Theorem to choose primes {q} so that most of the
powers 10i of 10 fall into the same congruence class for some prime q. This
made the argument effective enough to obtain several congruence conditions
(whose simultaneous solution exists by Chinese remainder theorem) with
a common solution to a small enough modulus so that Linnik’s Theorem
provides a solution which is a prime number. As in the case of the proof of
Theorem 1.1, Zsigmondy’s Theorem is going to be the key in our argument
to prove Theorem 1.3. Before we start giving the proof of the theorem, we
state the following technical lemma.
Lemma 2.4. Let A be a finite set of consecutive positive integers. For each
a ∈ A, and each integer i ≥ 2 for which the pair (a, i) is not an exception to
Zsigmondy’s theorem, let qa,i be a prime for which the order of a mod qa,i
is i. We can choose a family of disjoint sets {Qa}a∈A such that if we write
Qa = {qa,i1 < qa,i2 < qa,i3 < . . .}, then each difference ij+1 − ij ≤ 1 + #A.
Proof. We construct the sets Qa greedily. Proceed through the elements
a ∈ A in order. For each a, add to Qa the prime qa,i, where i is chosen as
small as possible subject to the conditions that
(1) qa,i is defined, and
(2) qa,i has not already been included in any of set Qa′ (a′ ∈ A).
Prime factors of the numbers resulting after a change of digits of primes 693
After having gone through the entire list of a’s, we start over and repeat
the process. We continue this indefinitely to construct the sets Qa.
Suppose that the prime added to Qa at a certain stage is qa,i. By the
next time we are to add a prime to Qa, we have used (in the worst case)
#A possible candidates. Since there is at most one index j ≥ 2 for which
qa,j is undefined, the prime we add at this next stage, say qa,i′ , necessarily
satisfies i′ − i ≤ #A+ 1, as desired. 
2.2. Proof of Theorem 1.3. Our proof strategy is as follows: First, note
that for an integer m coprime to j, if p ≡ −ahkj mod m then pj + a
hk ≡
0 mod m. In order to find primes p with the desired property, we attempt to
find residue classes to many (at least (log log x)1−ε) different prime moduli
in order for the numbers ahkj to be “covered”. One way to do this could
be assigning congruence conditions to each one of those numbers using
different moduli at each step. However this naive choice is not efficient
enough for our purpose: If we apply Chinese Remainder Theorem after
writing down lots of congruence conditions, the modulus to which we can
ensure a simultaneous solution would end up being too large to be able to
find small enough primes p in our range. Thus we would like to use the
same congruence classes for different ahkj , whenever there is no obstruction
to do so. Here, knowing that we can always find moduli for which a is far
from being a primitive root (by Zsigmondy’s Theorem) allows us to have
an efficient way to decrease the number of moduli we use at the end, and
the modulus we find the simultaneous solution for becomes much smaller,
allowing us to ensure that we can find prime solutions as small as we need
for our purpose.
We let K ≥ 2 be a given integer, and let ε > 0 be a fixed small real
number. For a given large x, we put t = bK log xc. Define the set
DK,t := {−K, −K + 1, . . . ,−1, 1, . . . ,K} × {0, 1, . . . , t} × {1, 2, . . . ,K},
so that #DK,t = 2K2(t+ 1).
First, put r := Kb(log x)
1
3 c. By Lemma 2.4, we can construct pairwise
disjoint sets {Qa}a∈{2,3,...K} as follows: each Qa = {qa,i1 < qa,i2 < . . .} and
the indices il satisfy K ≤ i1 < i2 < · · · ≤ r, and il− il−1 ≤ K, for all l > 1.
We enforce i1 ≥ K, so that Qa has no element ≤ K, while including only
elements indexed by il ≤ r ensures that the number of elements in Qa is at
most r −K + 1. We put Ia := {i1, i2, . . . : qa,il ∈ Qa}.
Now, let n = d(log log x)1−εe and let 1 ≤ d ≤ n be an integer. Here, n is
the number of times we will repeat our argument, and we will divide the pro-
cess into n pieces associated to the congruence classes modulo n (we use con-
gruence classes as a bookkeeping measure, this division may have been done
694 Kübra Benlı̇
in a different way without changing the result). We determine several con-
gruence classes (mod qa,il), for il ∈ Ia such that l = d+ en, inductively on
e. Fix any congruence class −ua,id (mod qa,id), then suppose that we have
determined the congruences −ua,id+en (mod qa,id+en), for each 0 ≤ e ≤ c−1.
Let C aid+cn be the set of numbers of the form
k·ah
j , (k, h, j) ∈ DK,t which are
not congruent to any of −ua,id+en mod qa,id+en , for any 0 ≤ e ≤ c−1. (Here
k·ah
j ≡ −u is equivalent to saying that k · a
h ≡ −ju.) Now, since the pow-
ers of a take exactly id+cn distinct values (mod qa,id+cn), numbers of the
form k·ahj can occupy at most 2K
2 id+cn residue classes (mod qa,id+cn). So
by the Pigeonhole Principle, there exists −uid+cn for which the congruence
class −ua,id+cn (mod qa,id+cn) is occupied by at least
⌈ #C aid+cn
2K2id+cn
⌉
elements
of C aid+cn .
We use the bounds for C ail for various l ≡ d mod n iteratively to obtain
that for given integers a and d, 1 ≤ d ≤ n, 2 ≤ a ≤ K, the number Rd,a
of triples (k, h, j) ∈ DK,t for which ka
h
j is not ≡ −ua,il mod qa,il for any
K ≤ il ≤ r, l ≡ d mod n is
≤ 2K2(t+ 1)
∏
il∈Ia
l≡d mod n
(
1− 12K2 il
)
.(2.3)
In order to assign congruence classes for the remainders from each step
of this process, we now list the numbers labeled by the triples counted
by
∑n
d=1Rd,a, meaning that the remaining elements of the form ka
h
j not
covered by the chosen residues classes for each 1 ≤ d ≤ n. We introduce
the notation given by the list: {va,d,f : 1 ≤ f ≤ Rd,a, 2 ≤ a ≤ K, 1 ≤
d ≤ n}. For each element in this list we assign a prime number among
the first
∑K
a=2
∑n
d=1Rd,a + rK primes which are not in ∪Ka=2Qa, denoted
by the elements of the following list: {Qa,d,f : 1 ≤ f ≤ Rd,a, 2 ≤ a ≤
K, 1 ≤ d ≤ n}. Note that the number of primes in ∪Ka=2Qa is at most
(K − 1)(r −K + 1) ≤ rK.
Using the construction above, we consider the following system of con-
gruences:
(2.4)
p ≡ ua,il mod qa,il , il ∈ Ia, 2 ≤ a ≤ K,
p ≡ −va,d,f mod Qa,d,f , 1 ≤ f ≤ Rd,a, 2 ≤ a ≤ K, 1 ≤ d ≤ n.
By the Chinese Remainder Theorem, the solution to the system of con-
gruences (2.4) is unique modulo (
∏
qa,il
∏
Qa,d,f ). If a prime p is a solution
to (2.4), then for all triples (k, h, j) ∈ DK,t, each pj + ahk is ≡ 0 modulo
at least n distinct primes. Indeed, let (k, h, j) ∈ DK,t. For every 1 ≤ d ≤ n,
in the above construction we determine a congruence class modulo a prime
Prime factors of the numbers resulting after a change of digits of primes 695
among either {qa,il} or {Qa,d,f} occupied by ka
h
j , call this class −u mod q.
Then p ≡ u mod q ≡ −kahj mod q which is equivalent to the congruence
pj + ahk ≡ 0 mod q. So for each pj + ahk, we have at least n distinct
primes q (one for each choice of d) dividing pj + ahk.
Next, we show that the modulus (
∏
qa,il
∏
Qa,d,f ) is not too large. First
note that, by the construction of Qa, for any a ∈ {2, 3, . . .K}, and l ≥ 1
such that qa,il ∈ Qa, we have K ≤ il and 0 < il+1− il ≤ K. Moreover, using
the construction given in Lemma 2.2 for the sets Qa, we have i1 ≤ 2K + 2.
So for any 2 ≥ d ≥ n, we have id ≤ i1 +dK ≤ (d+2)K+2, and similarly we
have id+en ≤ (d+ en+ 2)K+ 2. Note that there will be at least
⌊
r−(d+4)K
nK
⌋
elements of the form id+en, since the il only go up to r.
Therefore,
∑
il∈Ia
l≡d mod n
1
il
≥
⌊
r−(d+4)K
nK
⌋∑
e=0
1
(d+ en+ 2)K + 2
≥ 1
K
⌊
r−(d+4)K
nK
⌋∑
e=0
1
d+ en+ 3 ≥
1
nK
⌊
r−(d+4)K
nK
⌋∑
e=0
1
e+ 5 .
Since
r − (d+ 4)K
(n+ 1)K ≥ (log x)
1
4 ,
for large x, we have that∑
il∈Ia
l≡d mod n
1
il
≥ 1
nK
(1
5 log log x
)
 (log log x)
ε
2 .
Thus,∏
il∈Ia
l≡d mod n
(
1− 12K2il
)
≤ exp
{ −1
2K2 (log log x)
ε
2
}
 exp
{
−(log log x)
ε
3
}
.
Hence, recalling the upper bound in (2.3), we obtain
K∑
a=2
n∑
d=1
Rd,a K K2t
K∑
a=2
n∑
d=1
exp
{
−(log log x)
ε
3
}
K n log x exp
{
−(log log x)
ε
3
}
K
log x log log x
(log log x)ε exp{(log log x)
ε
3 }
K
log x
exp{(log log x)
ε
4 }
.
696 Kübra Benlı̇
Since the product of the first ` primes is exp{(1 + o(1))` log `}, and since
the primes labeled by Qa,d,f lie in the first
∑K
a=2
∑n
d=1Rd,a + rK primes,
we have the following upper bound for the product
∏
Qa,d,f :∏
Qa,d,f K exp
C ′ log x log log xexp{(log log x) ε4}
K x ε2 .(2.5)
On the other hand, as for each qa,il ∈ Qa, qa,il ≤ ail ,
K∏
a=2
∏
il∈Ia
qa,il ≤
K∏
a=2
r∏
h=1
ah ≤ (K!)
r(r+1)
2 K exp{C(log x)
2
3 } K x
ε
2 .(2.6)
Thus, combining (2.5) and (2.6), we seek for primes in a certain arith-
metic progression where the modulus is xε. Hence we apply Corollary 2.2
to finish the proof of Theorem 1.3. 
References
[1] G. D. Birkhoff & H. S. Vandiver, “On the Integral Divisors of an − bn”, Ann. Math. 5
(1904), no. 4, p. 173-180.
[2] E. Bombieri, Le grand crible dans la théorie analytique des nombres, Astérisque, vol. 18,
Société Mathématique de France, 1987.
[3] P. Erdős, “Solution to problem 1029: Erdős and the computer”, Math. Mag. 52 (1979),
p. 180-181.
[4] U. V. Linnik, “On the least prime in an arithmetic progression. I. The basic theorem”, Mat.
Sb., N. Ser. 15 (1944), no. 57, p. 139-178.
[5] H. Pan, “On the number of distinct prime factors of nj+ ahk”, Monatsh. Math. 175 (2014),
no. 2, p. 293-305.
[6] T. Tao, “A remark on primality testing and decimal expansions”, J. Aust. Math. Soc. 91
(2011), no. 3, p. 405-413.
Kübra Benlı̇
Department of Mathematics
University of Georgia
Athens GA 30602, USA
E-mail: kubra.benli25@uga.edu


On the number of prime factors of the composite numbers resulting after a change of digits of primes

Jason Bell

Rahim Moosa

$F$-sets and finite automata

Not a member yet

Optimalité pour un problème de Bézivin

Periodic Jacobi–Perron expansions associated with a unit II

A logarithmic improvement in the Bombieri–Vinogradov theorem

A uniform estimate for the density of rational points on quadrics

Near Counterexamples to Weil’s Converse Theorem

A measure of transcendence for singular points on conics

Concentrations simultanées de fonctions additives

Configurations of Extremal Type II Codes via Harmonic Weight Enumerators

On the number of prime factors of the composite numbers resulting after a change of digits of primes

$F$ -sets and finite automata

1,235

1,351