WorksMathematics
A solution to the Erdős-Sárközy product-density problem
Abstract
Color each positive integer red or blue, and call an integer a same-color product if it is the product of two red numbers or of two blue numbers. Does there exist a universal constant such that: For each fixed coloring, and for all sufficiently large (where "sufficiently large" may depend on the coloring), at least of the integers among , , , are same-colored products (allowing for equal factors, and where each distinct product is counted once)? This problem was given (in an equivalent way) in Guy's famous text on unsolved problems in number theory, and was posed (in equivalent ways) by Erdős and Sárközy in 1990, in the proceedings of the 1988 Banff number theory conference, and 1993 [Colloq. Math.], and this problem seems to have remained open. We succeed in solving this problem, by proving that no such universal constant exists.
Introduction
Multiplicative Ramsey theory is a deep and challenging area in combinatorial number theory. A foundational reference in multiplicative Ramsey theory is due to Hindman [9], who introduced and proved a result that gives that each finite coloring of admits a strictly increasing infinite sequence such that each nonempty finite product of distinct terms has the same color. Some similarly notable works are due to Bergelson et al. [2, 3], Green and Sanders [7], and Moreira [10]. We solve, building on our extensive interactions with GPT-6 Astra Pro, a problem in the field of multiplicative Ramsey theory that is given in Guy’s classic textbook on unsolved problems in number theory [8 p. 204] and that was repeatedly posed by Erdős and Sárközy [5, 6]. It appears that this problem has, prior to our work, remained open.
Erdős and Sárközy [5, 6] pose the following question: For each , is it true that there is a partition of such that the lower asymptotic density of the sequence consisting of the distinct monochromatic products is less than ? In this context, a positive integer is said to be a monochromatic product if it admits at least one factorization of the form such that the two factors and are either both in or are both in . In this paper, we answer Erdős and Sárközy’s question in the
2020 Mathematics Subject Classification. Primary 11B05; Secondary 05D10.
Key words and phrases. lower asymptotic density, multiplicative Ramsey theory, combinatorial number theory, monochromatic products. affirmative. The problem given by determining whether or not this question holds is equivalent to a problem in Guy’s classic text on unsolved problems in number theory [8 p. 204], in the sense that a solution to one problem gives a solution to the other problem. More specifically, a negative solution to Guy’s problem is equivalent to a solution in the affirmative to the Erdős–Sárközy problem. For every fixed finite partition, the lower density of the monochromatic products is positive [5], but what is at issue is whether that positive lower bound can be chosen independently of the partition.
For a 2-coloring of , write
and
Thus the Erdős–Sárközy problem above is given by whether or not it is the case that
As suggested in the above abstract, the problem given by whether or not (3) holds is equivalent to the problem as to whether or not the negation
holds. More precisely, and in view of (2), we find that (4) is equivalent (as clarified below) to
i.e., for a universal constant . To justify this equivalence, if, for fixed and for each coloring , we have that , then, for every coloring , we have that for sufficiently large . Conversely, if, for fixed and for every coloring , we have that for sufficiently large , then . As indicated above, we prove that no universal constant of the form indicated above can exist, thus proving (3) in the affirmative.
Example 1. Let each odd and positive integer be colored red. Let each even and positive integer be colored blue. According to this coloring, for a positive integer , let denote the number of distinct monochromatic products among . For example, we see that , since the associated monochromatic products are as shown below.
Observe that does not qualify, and observe that also does not qualify. It is easily seen (omitting details) that the integer sequence , as defined above, may be explicitly evaluated so that
This agrees with the sequence indexed in the On-line Encyclopedia of Integer Sequences1 as A037915, but there is not currently any equivalent definition of , as defined above, given. From the evaluation in (5), we find that, according to the specified coloring , and with respect to the notation in (1), the evaluation holds.
The problem indicated above may be seen in relation to subsequent work related to the given Erdős–Sárközy references [5, 6]. Csikvári et al. [4 Theorem 7] use the logarithmic-density theorem for monochromatic products from Erdős and Sárközy [5] to establish positive lower logarithmic density for integers admitting both monochromatic sum and product representations, with the two representations allowed to use different colours. However, this result does not settle the two-class lower-asymptotic-density problem studied here. The Erdős–Sárközy problem above may also be seen in contrast to a related problem on colorings of sums of integers, as opposed to products of integers, with reference to the so-called Erdős Problem #48422.
Main construction
We begin by covering some basic preliminaries. In this direction, for a subset of the set of positive integers, we write in place of (where repeated factor are permitted). For subsets and contained in , we write
We require some familiar arithmetic functions, and, in this direction, we recall the prime-counting function giving the number primes less than or equal to a given real value , and we let denote the exponent of in the prime factorization of the positive integer . Throughout, sums indexed by are understood as being over primes.
We also require some basic properties of the special function known as the digamma function, which may be defined so that for and for the familiar -function, referring to Rainville’s classic text for background [11 §2]. For the Euler–Mascheroni constant ), a fundamental property of the digamma function is such that
for real . A consequence of a result due to Alzer and Berg [1, Theorem 4.2(i)] is such that
for , which follows from the mapping being nonincreasing on .
We require, for the purposes of the proof below, a well known consequence of Markov’s inequality. This may be seen as a “non-probabilistic” version of Markov’s inequality, and this may be formulated as follows. Suppose that is a finite set. Then, for a mapping and for a positive value , the relation
holds.
Some further notation local to our construction is given as follows. By letting be real, we write
noting that the condition guarantees that . Recall that a fundamental result in number theory (attributed to Euler) is such that as . Now, for a real value , define
The definition in (11) leads us toward Lemma 1 below.
Lemma 1. Let . Suppose that
and suppose that
for real values and . Then
for (noting that since ).
Proof. Write for brevity (again noting that from the hypothesis in (12)). We then define
letting indicator functions be denoted as per usual. We also define
For a real value , we find that
Applying the relation to the positive terms, and applying the relation in the negative terms, we find that
Since
the relation in (16) gives us that
Now, consider the families among
Since and since , either case gives us that . This and (18) together give us that each of the families indicated in (19) has at most members. Also, by using the evaluation , we find that
Now, since (recalling (15)) and since (recalling (10)), by applying the consequence of Markov’s inequality on display in (9) to the function , with and with , we find that
so that a joint application of (20) and (21) gives us that
This leads us toward the following case analysis, where the cases below correspond to the conditions associated with the sets of the forms and defined below.
Case 1. Define
and, for each , define
Taking in the established bound for the first set in (19), we obtain
Again for in the family defined in (23), since , we find that
The union is exactly the set of positive integers having at least one divisor in . Consequently, an application of the inclusion–exclusion principle gives us that . This and (24) and (25) together give us that
Case 2. Define
and, for each element , define
For a fixed integer in , we find that
From the hypothesis indicated in (13), we find that (30) implies that
The relation in (31) allows us to let , recalling that . So, from the established upper bound for the first family on display in (19), we find that
We rewrite (32) so that , and this then gives us that
For each member in the family whose cardinality is given as the left-hand side of the inequality in (33), we obtain a different value of . So, again for a given fixed value of , there are (according to (33)) at most integers admitting a factorization of the form such that .
It is immediate that the right-hand side of (28) has the same cardinality as . So, from the relation in (32), we find that . This and an application of the inclusion–exclusion principle give us that
Since is increasing on (and this may be seen via the series expansion shown in (7)), and since the recurrence holds, a telescoping argument and the Alzer–Berg inequality in (8) (applied with and ) give us that
noting that this last inequality holds since , i.e., from the hypothesis displayed in (12). A combined application of the given bounds for and gives us that
Case 3. Let be as in (28), and, for each member in , define
Let , and write . From the definition in (14), we find that
Now, observe that a given prime dividing both and is such that and thus contributes at least 1 as a term on the right-hand side of (15). From (36), we thus have that
From (37) and the assumptions that and that , we find that
From (38), we obtain the implication . So, each member in is such that or . Since this holds for an arbitrary member of , and since the definition in (35) gives us that each member in is , we find that the inclusion
holds, and we thus obtain that
From (12) and (13) together, we find that . This allows us (recalling that , as in (17)) to set , i.e., in the established bounds for the latter family in (19) and in the bound on display in (23). Using these established bounds, the above bound for gives us that
Now, recall the definition of on display in (11), giving a family of positive integers admitting a factorization for positive integers and , with . Each such factorization satisfies one of the conditions used to define Cases 1–3, so that
So, a combined application of the inequalities among (27), (34), (39), and (40) gives us that
as desired. □
Lemma 2. Let and let . Then there exist a strictly increasing sequence of positive integers and a set
such that:
(a) Each bounded interval contains only finitely many elements of ;
(b) For each positive integer , the value is in ;
(c) The elements in are such that
and
(d) The function
defined for and is such that
for and
Proof. Our strategy is to construct the terms of the desired sequence recursively, starting with . Similarly, we recursively construct a sequence of finite sets to define , with
Also, define . Now, for an index , with the assumption that and have already been determined, we proceed to choose a positive integer satisfying both
and
noting that such a selection is permitted by the classical result giving that the right-hand side of (10) approaches as . Having chosen (subject to the given conditions), we proceed to define
and
From (45) and (47) together, we obtain that
for , thus giving us that is strictly increasing and consists of positive integers. Now, since is a positive integer, and since , we find that is not a perfect square, so that is irrational for each index . Since , the recursion in (49) gives us that . Since is positive and irrational (as established), we find that is a finite set of positive irrational numbers. Also observe that is positive and irrational whenever is positive and irrational. So, the recursive definition for and the irrationality of together show that is necessarily a finite set consisting of positive and irrational numbers, for each index . We proceed to prove, via induction, that
for each index .
For the base case, with , we find that and that , directly from the definition in (46). Similarly, from (48), we find that . So, since , the inclusion in (51) holds for the current base case. Now, for an index , we (inductively) assume that
Now, for each element , the inductive hypothesis in (52) gives us that . Also, from (46), we find that
Also, from (48), we find that
i.e., so that
Again letting , from the induction hypothesis shown in (52), we find that . Moreover, from (53) and (54), we find that
From (56), we see that , which, in turn, implies
From (55) and (57), we obtain the inclusion
thus completing our induction.
Now, recall that we previously established that consists of irrational numbers. From this and (57) together, we find that
To prove the first assertion listed above, we begin by proving that
for each . Now, recall the relations among , , and shown in (55). By letting , we find, again with reference to (55) (recalling that (55) holds for ), that . So, the relations in (55) give us that
Now, from the recursion on display in (48), if is any element in , then either or for some .
In the former case, the definitions of and give us that
In the latter case, we have for some , and the previously established inequality gives us that
So, for every , the inclusion
holds.
We proceed to let be an arbitrary bounded interval, and we then let be a real value such that . As established previously (recalling (49)), the sequence is strictly increasing, and we also recall that it consists of positive integers. So, since , we are permitted to choose an index such that . For each , every member in is such that
and we thus find that
since . The recursion in (48) gives us that , and thus, for , we proceed to write
so that a combined application of (60) and (61) yields
A repeated application of the equality in (63) then gives us that
for each . Since
we find, by appealing to the equality in (64) that
Also observe that is finite, as a consequence of being finite. This proves the first listed assertion above.
The second listed assertion follows immediately from the recursion in (49) in conjunction with the definition in (45).
We now proceed to establishing the third assertion listed above. In this direction, we begin by observing that , , and are pairwise disjoint for an arbitrary element in , since: For each , we have that , recalling (56) and (60). For a fixed and positive integer , we find that the mapping on such that is injective, and we thus find that the recursion shown in (49) yields the recurrence such that
Since , this and the recurrence in (66) together give us that
for each nonnegative integer . Since (again recalling the recursion in (49)), this and the evaluation in (67) together give us that
for each positive integer . From the recursion in (49), a given element in (letting be fixed) is either equal to or is equal to for some . In the latter case, the relations in (60) (which hold, as above, for ) give us that , so, in either case, we see that . Now, since (recalling (54)), and since the mapping on such that is nondecreasing (recalling (10)), the defining condition in (47) gives us that
From (67) and (68) together, we find that
Since , , and for each , sets of the form are pairwise disjoint with union , an application of (70) gives us that
thus proving the third listed assertion as desired.
We proceed to prove the final listed assertion. In this direction, we begin by fixing a positive integer , and observing that (50) gives us that
Consequently, the relation
holds. From the chain of sets indicated in (64) together with the inclusion in (58) together with the -sequence being nondecreasing, we find that
Now, observe that the mapping on such that is a bijection, since, in view of the recursion in (48), the given mapping interchanges and and fixes . Now, let
be fixed. Since and are rational and since each element in is irrational, we find that neither nor is in . Now, since the given bijection maps onto itself, we see that this same bijection maps onto , and we thus obtain the equality
Recalling the inclusion in (71), since , we find that and form a partition of . This partition gives us that
A combined application of (67), (74), and (75) then gives us that
Recalling (73), we have that , with , so that
where the last equality in (77) follows from (72). From (73), we find that , i.e., so that . By analogy with (77), we have that
where we have again exploited (72). So, a combined application of (76), (77), and (78) yields
So, in view of the parity of , the definition of shown in (42) and the equalities in (79) together give us that
Since the possible values for are in , the preceding equalities give us that , and this proves the final listed assertion. □
We are now in a position to prove our main result and to provide an affirmative solution to the Erdős–Sárközy problem given in Section 1.
Theorem 1. For each , there exists a partition of such that
Proof. It suffices to prove the desired result for (since, once such a result is established for , it would immediately hold for larger values). So, let be fixed. Also, set and . Since and , Lemma 2 gives us a strictly increasing sequence of positive integers and a set satisfying the desired conditions in Lemma 2, along with the associated function for . We then define two color classes so that and . Since for each positive integer , we find that and form a partition of , defining a 2-coloring that we denote with .
Now, let be a fixed and positive integer, and write in place of . For any such that
there exists (recalling (6)) at least one factorization such that and and
We fix one such factorization . This leads us to two cases covered below.
Case 1. Suppose that . Then, by taking , as permitted by the second listed assertion in Lemma 2, we find that . From (79), we find that .
Case 2. Suppose that . Define
Since and since , we find that
and
From (82), we find that , and this and (81) together give us that , recalling the condition in (43) associated with the reflection identity in (42) for the -function. This same reflection identity, applied with , gives us that
where we have exploited both (80) and (81). This gives us that
Now, since and , we have that
Also, observe that (84) and (85) together give us that . Each member of is irrational, recalling (40), but is an integer and is rational. This leads us to the implications such that
thus contradicting (84), noting that we have exploited (to obtain the final implication in (86)) the definition of on display in (41). So, in view of the implications shown in (86), it cannot be the case that is empty. So, we have shown that there exists an element (noting that is nonempty by construction, with, for example, the value being in for all ) such that . For the given choice of , the inequality (recalling (82)) and the inequality (recalling (83)) give us that and that .
So, in either of the above cases, we have that and that . Now, let . So, in other words, the integer is a monochromatic product such that . We proceed to consider two separate cases.
Case 1. Suppose that . Then it is immediate that .
Case 2. Suppose that . From the preceding case analysis, we deduce that there exists a positive integer divisor and an element such that and .
We thus obtain the inclusion
Since (recalling (40)), we find that indexing sets associated with the latter union above consist of elements in . As established in Lemma 2, every bounded interval contains only finitely many elements of , and hence the finitude of . From this finitude, the above inclusion, and the definition in (11), we find that
Now, for such that , since a given element in is strictly greater than according to (40), we find that . Since , this yields . So, the required conditions of Lemma 1 hold for , writing
From (87) and (88), we find that
Since for each member in , this and the third listed assertion in Lemma 2 give us that
Now, recall that was arbitrary and that . Also recall that and that . A combined application of the relations among (89) and (90) gives us that
Since is a strictly increasing sequence of positive integers, we find that , and we thus find that
as desired. □
Example 2. For each , our construction, as above, gives us at least one coloring of such that . There are many such 2-colorings possible according to our construction, and this depends on how values of the form
, as in (45), are chosen. Adopting the convention that 1 is colored with red, our construction necessarily assigns colorings so that
For example, let . In this case, the associated parameters are , , and . By then writing , we define
The admissible choices for are thus , , etc. Using classical bounds for sums of reciprocals of consecutive primes due to Rosser and Schoenfeld [12 Theorem 5, Eq. (3.17)–(3.18)], it can be shown that
So, in any case, the first
integers would necessarily be colored red for the case.
Conclusion
Our solution to the Erdős–Sárközy product-density problem indicated above and the techniques introduced and employed above raise questions in regard to further areas of study related to the given problem and to our techniques. For example, instead of coloring each positive integer (red or blue) and then considering lower limits as in (2), we could instead color each prime (red or blue) and then enumerate integers up to a given integer that admit a monochromatic prime factorization. This is decidedly inequivalent to the enumeration suggested in (1), and we encourage a full exploration of monochromatic prime factorizations in relation to the work of Erdős and Sárközy [5, 6].
For a given value , how can we characterize 2-colorings of such that the limit exists and, moreover, is equal to (being consistent with the definition of in (1))?
How can we characterize 2-colorings of such that does not exist?
AI disclosure. The following AI disclosure is based on AI disclosures used and written by the author previously (with numerous parts taken verbatim from previous AI disclosures used and written by the author).
Our solution above to Guy’s problem is, as indicated above, based on our extensive interactions with GPT-6 Astra Pro, and this is described in more detail below. All AI-generated suggestions were substantially revised, corrected, and independently verified by the author, who assumes full responsibility for the mathematical content. The author’s use of AI is fully in accordance with editorial standards on the responsible, ethical, and transparent use of AI.
On 2026-10-18, the author inputted a prompt into GPT-6 Astra Pro containing an equivalent version of the problem from Guy’s text solved above (with an explicit attribution to Guy’s text on unsolved problems in number theory), concluding with an explicit request that GPT-6 Astra Pro solve the given problem. After 13m 53s of thinking, GPT-6 Astra Pro provided a response beginning with
“I obtain a negative answer to the exact formulation you gave: no such absolute constant exists. The construction below produces, for every , one fixed partition and an infinite sequence of cutoffs at which the proportion of distinct monochromatic products is at most .”
After extensive clarifications, corrections, revisions, suggestions, verifications, calculations, etc., through extensive discussions between the author and GPT-6 Astra Pro, and after extensive and careful reviews of such discussions on the part of the author, this provided a basis for the above solution, written by the author, to Guy’s problem.
For example, it was through the author’s enquiries, investigations, revisions, reviews, reflections, considerations, etc., that the “non-probabilistic” version of Markov’s inequality given above was employed to prove Lemma 1. Similar commentary applies to the case analysis in the proof of Lemma 1, the use of the Alzer–Berg inequality in (8), the expansion of involved in the proof of Lemma 1, the equivalent formulations of the Erdős–Sárközy problem discussed in § 1, the evaluation in (5), etc.
Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada
Email address: [email protected]
References
- [2]Mathias Beiglböck, Vitaly Bergelson, Neil Hindman, and Dona Strauss. Some new results in multiplicative and additive Ramsey theory. Trans. Amer. Math. Soc., 360(2):819–847, 2008.DOI
- [3]Vitaly Bergelson. Multiplicatively large sets and ergodic Ramsey theory. volume 148, pages 23–40. 2005. Probability in mathematics.DOI
- [4]Péter Csikvári, Katalin Gyarmati, and András Sárközy. Density and Ramsey type results on algebraic equations with restricted solution sets. Combinatorica, 32(4):425–449, 2012.DOI
- [5]P. Erdős and A. Sárközy. On a conjecture of Roth and some related problems. II. In Number theory (Banff, AB, 1988), pages 125–138. de Gruyter, Berlin, 1990.
- [6]P. Erdős and A. Sárközy. Some solved and unsolved problems in combinatorial number theory. II. Colloq. Math., 65(2):201–211, 1993.DOI
- [7]Ben Green and Tom Sanders. Monochromatic sums and products. Discrete Anal., pages Paper No. 5, 48, 2016.DOI
- [8]Richard K. Guy. Unsolved problems in number theory. Problem Books in Mathematics. Springer-Verlag, New York, second edition, 1994. Unsolved Problems in Intuitive Mathematics, I.
- [9]Neil Hindman. Partitions and sums and products of integers. Trans. Amer. Math. Soc., 247:227–245, 1979.DOI
- [10]Joel Moreira. Monochromatic sums and products in N. Ann. of Math. (2), 185(3):1069–1090, 2017.arxiv.org/abs/1605.01469
- [11]Earl D. Rainville. Special functions. The Macmillan Company, New York, 1960.
- [12]J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math., 6:64–94, 1962.