Journal de Théorie des Nombres de Bordeaux

Christopher Keyes

Growth of points on hyperelliptic curves over number fields

Florian Viguier

Transformée de Fourier–Mukai sur les schémas formels

Étienne Fouvry

Peter Koymans

On Dirichlet biquadratic fields

Beáta Bényi

Toshiki Matsusaka

Combinatorial aspects of poly-Bernoulli polynomials and poly-Euler numbers

Tim Santens

Integral points on affine quadric surfaces

Jorge Mello

On abelian points of varieties intersecting subgroups in a torus

María Inés de Frutos-Fernández

Moduli Spaces of Shtukas over the Projective Line

Béla Bollobás

Béla BOLLOBÁS
Remarks on a paper of J. Barát and P.P. Varjú
Tome 34, no 2 (2022), p. 515-516.
https://doi.org/10.5802/jtnb.1212
© Les auteurs, 2022.
Cet article est mis à disposition selon les termes de la licence
CREATIVE COMMONS ATTRIBUTION – PAS DE MODIFICATION 4.0 FRANCE.
http://creativecommons.org/licenses/by-nd/4.0/fr/
C EN T R E
MER S ENN E
Le Journal de Théorie des Nombres de Bordeaux est membre du
Centre Mersenne pour l’édition scientifique ouverte
http://www.centre-mersenne.org/
e-ISSN : 2118-8572
Journal de Théorie des Nombres
de Bordeaux 34 (2022), 515–516
Remarks on a paper of J. Barát and P.P. Varjú
par Béla BOLLOBÁS
Résumé. Soit {din + bi : n ∈ Z}i∈I une famille de suites arithmétiques qui
est une couverture disjointe de l’ensemble des nombres entiers. Barát and
Varjú [1] ont prouvé que si di = pα11 p
α2
2 pour deux nombres premiers p1, p2
et des entiers α1, α2 ≥ 0, alors il existe i et j tels que j 6= i et di|dj . Nous
montrons que ce résultat reste vrai si di = pα11 . . . pαnn pour un ensemble fixé
{p1, . . . , pn} de n nombres premiers.
Abstract. Let {din + bi : n ∈ Z}i∈I be a family of disjoint arithmetic
progressions covering the integers. Barát and Varjú [1] have proved that if
di = pα11 p
α2
2 for two prime numbers p1, p2 and integers des α1, α2 ≥ 0, then
there exist j 6= i such that di|dj . We show that this result remains true if
di = pα11 . . . pαnn for a fixed set {p1, . . . , pn} of n prime numbers.
Covering systems were introduced by Paul Erdős [3] in 1950. In parti-
cular, a disjoint covering system (DCS) is an infinite collection of pairwise
disjoint infinite arithmetic progressions A(di, bi) = {ndi + bi : n ∈ Z}
whose union is Z. One of the early results about disjoint covering systems,
proved by Mirsky, Newman, Davenport, Rado and Stein (see [4]) is that in
a finite disjoint covering system the two largest moduli are equal. For an
infinite DCS, the case n = 2 of the following result was proved by Barát
and Varjú [1].
Theorem 1. If {A(di, bi) : i ∈ I} is an infinite DCS such that the prime
factors of each modulus di belong to the same finite set of primes, then di|dj
for some i 6= j.
Our aim in this note is to point out that the considerably stronger Theo-
rem 2 below, which has nothing to do with covering systems, is an old (and
simple) result in combinatorics.
Theorem 2. Let {di : i ∈ I} be an infinite set of natural numbers such
that the prime factors of each di belong to a set P = {p1, . . . , pn} of n
primes. Then di|dj for some i 6= j.
Manuscrit reçu le 28 novembre 2020, accepté le 19 avril 2021.
Mathematics Subject Classification. 11B25.
Mots-clefs. Arithmetic progression, covering.
Partially supported by NSF grant DMS 1600742.
516 Béla Bollobás
To restate this assertion, let (Nn,≺) be the partially ordered set with
the partial order x = (xi)n1 ≺ y = (yi)n1 ∈ Nn if xi ≤ yi for every i and
x 6= y. As in every poset, a set A ⊂ Nn is an antichain if a 6= b ∈ A
implies that a 6≺ b, i.e. bj < aj for some j. Identifying ni = pα11 . . . pαnn with
the n-tuple (α1 + 1, . . . , αn + 1) ∈ Nn, Theorem 2 has the following simple
reformulation.
Theorem 3. In the poset (Nn,≺) every antichain is finite.
Although this is Dickson’s Lemma [2] from 1913, let us prove it by in-
duction on n, starting with the trivial case n = 1. Suppose that n ≥ 2
and the assertion holds for smaller values of n. For 1 ≤ j ≤ n and k ≥ 1,
let Mj(k) = {x = (xi)n1 ∈ Nn : xj = k}, and note that (Mj(k),≺) is
isomorphic to (Nn−1,≺).
Let A ⊂ Nn be an antichain and let a = (ai)n1 ∈ A. If b ∈ A and b 6= a
then b ∈Mj(k) for some j and k with 1 ≤ j ≤ n and 1 ≤ k ≤ aj − 1. Since
A ∩Mj(k) is an antichain in (Mj(k),≺) ∼= (Nn−1,≺), it is a finite set by
the induction hypothesis. Consequently, A is also finite.
This result is the starting point of the rich and deep theory of well-
quasi-ordered sets: for a review of the early results, see Kruskal [5], and for
highlights of an important series of papers on graph minors, see Robertson
and Seymour [6, 7].
References
[1] J. Barát & P. P. Varjú, “A contribution to infinite disjoint covering systems”, J. Théor.
Nombres Bordeaux 17 (2005), no. 1, p. 51-55.
[2] L. E. Dickson, “Finiteness of the odd perfect and primitive abundant numbers with n distinct
prime factors”, Am. J. Math. 35 (1913), p. 413-422.
[3] P. Erdős, “On integers of the form 2k +p and some related problems”, Summa Brasil. Math.
2 (1950), p. 113-123.
[4] ———, “Quelques problèmes de théorie des nombres”, in Introduction à la théorie des nom-
bres, Monographies de l’Enseignement Mathématique, vol. 6, L’Enseignement Mathématique,
1963, p. 81-135.
[5] J. B. Kruskal, “The theory of well-quasi-ordering: A frequently discovered concept”, J.
Comb. Theory, Ser. A 13 (1972), p. 297-305.
[6] N. Robertson & P. D. Seymour, “Graph minors XIX, Well-quasi-ordering on a surface”,
J. Comb. Theory, Ser. B 90 (2004), no. 2, p. 325-385.
[7] ———, “Graph minors XX, Wagner’s conjecture”, J. Comb. Theory, Ser. B 92 (2004), no. 2,
p. 325-357.
Béla Bollobás
Department of Pure Mathematics and Mathematical Statistics,
Wilberforce Road,
Cambridge, CB3 0WA, UK
and
Department of Mathematical Sciences,
University of Memphis,
Memphis, TN 38152, USA
E-mail: b.bollobas@dpmms.cam.ac.uk


Not a member yet

Growth of points on hyperelliptic curves over number fields

Transformée de Fourier–Mukai sur les schémas formels

On Dirichlet biquadratic fields

Combinatorial aspects of poly-Bernoulli polynomials and poly-Euler numbers

Integral points on affine quadric surfaces

On abelian points of varieties intersecting subgroups in a torus

Moduli Spaces of Shtukas over the Projective Line

Remarks on a paper of J. Barát and P.P. Varjú

Idéaux premiers totalement décomposés et sommes de Newton

A note on finite embedding problems with nilpotent kernel

1,235

1,351