I’ve just uploaded to the arXiv my paper “On product representations of squares“. This short paper answers (in the negative) a (somewhat obscure) question of Erdös. Namely, for any
, let
be the size of the largest subset
of
with the property that no
distinct elements of
multiply to a square. In a paper by Erdös, Sárközy, and Sós, the following asymptotics were shown for fixed
:
Thus the asymptotics for
![{F_k(N)}](https://s0.wp.com/latex.php?latex=%7BF_k%28N%29%7D&bg=ffffff&fg=000000&s=0&c=20201002)
for odd
![{k \geq 5}](https://s0.wp.com/latex.php?latex=%7Bk+%5Cgeq+5%7D&bg=ffffff&fg=000000&s=0&c=20201002)
were not completely settled. Erdös asked if one had
![{F_k(N) = (1-o(1)) N}](https://s0.wp.com/latex.php?latex=%7BF_k%28N%29+%3D+%281-o%281%29%29+N%7D&bg=ffffff&fg=000000&s=0&c=20201002)
for odd
![{k \geq 5}](https://s0.wp.com/latex.php?latex=%7Bk+%5Cgeq+5%7D&bg=ffffff&fg=000000&s=0&c=20201002)
. The main result of this paper is that this is not the case; that is to say, there exists
![{c_k>0}](https://s0.wp.com/latex.php?latex=%7Bc_k%3E0%7D&bg=ffffff&fg=000000&s=0&c=20201002)
such that any subset
![{A}](https://s0.wp.com/latex.php?latex=%7BA%7D&bg=ffffff&fg=000000&s=0&c=20201002)
of
![{\{1,\dots,N\}}](https://s0.wp.com/latex.php?latex=%7B%5C%7B1%2C%5Cdots%2CN%5C%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
of cardinality at least
![{(1-c_k) N}](https://s0.wp.com/latex.php?latex=%7B%281-c_k%29+N%7D&bg=ffffff&fg=000000&s=0&c=20201002)
will contain
![{k}](https://s0.wp.com/latex.php?latex=%7Bk%7D&bg=ffffff&fg=000000&s=0&c=20201002)
distinct elements that multiply to a square, if
![{N}](https://s0.wp.com/latex.php?latex=%7BN%7D&bg=ffffff&fg=000000&s=0&c=20201002)
is large enough. In fact, the argument works for all
![{k \geq 4}](https://s0.wp.com/latex.php?latex=%7Bk+%5Cgeq+4%7D&bg=ffffff&fg=000000&s=0&c=20201002)
, although it is not new in the even case. I will also note that there are now quite sharp upper and lower bounds on
![{F_k}](https://s0.wp.com/latex.php?latex=%7BF_k%7D&bg=ffffff&fg=000000&s=0&c=20201002)
for even
![{k \geq 4}](https://s0.wp.com/latex.php?latex=%7Bk+%5Cgeq+4%7D&bg=ffffff&fg=000000&s=0&c=20201002)
, using methods from graph theory: see
this recent paper of Pach and Vizer for the latest results in this direction. Thanks to the
results of Granville and Soundararajan, we know that the constant
![{c_k}](https://s0.wp.com/latex.php?latex=%7Bc_k%7D&bg=ffffff&fg=000000&s=0&c=20201002)
cannot exceed the
Hall-Montgomery constant ![\displaystyle 1 - \log(1+\sqrt{e}) + 2 \int_1^{\sqrt{e}} \frac{\log t}{t+1}\ dt = 0.171500\dots](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++1+-+%5Clog%281%2B%5Csqrt%7Be%7D%29+%2B+2+%5Cint_1%5E%7B%5Csqrt%7Be%7D%7D+%5Cfrac%7B%5Clog+t%7D%7Bt%2B1%7D%5C+dt+%3D+0.171500%5Cdots&bg=ffffff&fg=000000&s=0&c=20201002)
and I (very tentatively) conjecture that this is in fact the optimal value for this constant. This looks somewhat difficult, but a more feasible conjecture would be that the
![{c_k}](https://s0.wp.com/latex.php?latex=%7Bc_k%7D&bg=ffffff&fg=000000&s=0&c=20201002)
asymptotically approach the Hall-Montgomery constant as
![{k \rightarrow \infty}](https://s0.wp.com/latex.php?latex=%7Bk+%5Crightarrow+%5Cinfty%7D&bg=ffffff&fg=000000&s=0&c=20201002)
, since the aforementioned result of Granville and Soundararajan morally corresponds to the
![{k=\infty}](https://s0.wp.com/latex.php?latex=%7Bk%3D%5Cinfty%7D&bg=ffffff&fg=000000&s=0&c=20201002)
case.
In the end, the argument turned out to be relatively simple; no advanced results from additive combinatorics, graph theory, or analytic number theory were required. I found it convenient to proceed via the probabilistic method (although the more combinatorial technique of double counting would also suffice here). The main idea is to generate a tuple
of distinct random natural numbers in
which multiply to a square, and which are reasonably uniformly distributed throughout
, in that each individual number
is attained by one of the random variables
with a probability of
. If one can find such a distribution, then if the density of
is sufficienly close to
, it will happen with positive probability that each of the
will lie in
, giving the claim.
When
, this strategy cannot work, as it contradicts the arguments of Erdös, Särközy, and Sós. The reason can be explained as follows. The most natural way to generate a triple
of random natural numbers in
which multiply to a square is to set
![\displaystyle \mathbf{n}_1 := \mathbf{d}_{12} \mathbf{d}_{13}, \mathbf{n}_2 := \mathbf{d}_{12} \mathbf{d}_{23}, \mathbf{n}_3 := \mathbf{d}_{13} \mathbf{d}_{23}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathbf%7Bn%7D_1+%3A%3D+%5Cmathbf%7Bd%7D_%7B12%7D+%5Cmathbf%7Bd%7D_%7B13%7D%2C+%5Cmathbf%7Bn%7D_2+%3A%3D+%5Cmathbf%7Bd%7D_%7B12%7D+%5Cmathbf%7Bd%7D_%7B23%7D%2C+%5Cmathbf%7Bn%7D_3+%3A%3D+%5Cmathbf%7Bd%7D_%7B13%7D+%5Cmathbf%7Bd%7D_%7B23%7D&bg=ffffff&fg=000000&s=0&c=20201002)
for some random natural numbers
![{\mathbf{d}_{12} \mathbf{d}_{13}, \mathbf{d}_{23}}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bd%7D_%7B12%7D+%5Cmathbf%7Bd%7D_%7B13%7D%2C+%5Cmathbf%7Bd%7D_%7B23%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
. But if one wants all these numbers to have magnitude
![{\asymp N}](https://s0.wp.com/latex.php?latex=%7B%5Casymp+N%7D&bg=ffffff&fg=000000&s=0&c=20201002)
, one sees on taking logarithms that one would need
![\displaystyle \log \mathbf{d}_{12} + \log \mathbf{d}_{13}, \log \mathbf{d}_{12} + \log \mathbf{d}_{23}, \log \mathbf{d}_{13} + \log \mathbf{d}_{23} = \log N + O(1)](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Clog+%5Cmathbf%7Bd%7D_%7B12%7D+%2B+%5Clog+%5Cmathbf%7Bd%7D_%7B13%7D%2C+%5Clog+%5Cmathbf%7Bd%7D_%7B12%7D+%2B+%5Clog+%5Cmathbf%7Bd%7D_%7B23%7D%2C+%5Clog+%5Cmathbf%7Bd%7D_%7B13%7D+%2B+%5Clog+%5Cmathbf%7Bd%7D_%7B23%7D+%3D+%5Clog+N+%2B+O%281%29&bg=ffffff&fg=000000&s=0&c=20201002)
which by elementary linear algebra forces
![\displaystyle \log \mathbf{d}_{12}, \log \mathbf{d}_{13}, \log \mathbf{d}_{23} = \frac{1}{2} \log N + O(1),](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Clog+%5Cmathbf%7Bd%7D_%7B12%7D%2C+%5Clog+%5Cmathbf%7Bd%7D_%7B13%7D%2C+%5Clog+%5Cmathbf%7Bd%7D_%7B23%7D+%3D+%5Cfrac%7B1%7D%7B2%7D+%5Clog+N+%2B+O%281%29%2C&bg=ffffff&fg=000000&s=0&c=20201002)
so in particular each of the
![{\mathbf{n}_i}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bn%7D_i%7D&bg=ffffff&fg=000000&s=0&c=20201002)
would have a factor comparable to
![{\sqrt{N}}](https://s0.wp.com/latex.php?latex=%7B%5Csqrt%7BN%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
. However, it follows from known results on the “
multiplication table problem” (how many distinct integers are there in the
![{n \times n}](https://s0.wp.com/latex.php?latex=%7Bn+%5Ctimes+n%7D&bg=ffffff&fg=000000&s=0&c=20201002)
multiplication table?) that most numbers up to
![{N}](https://s0.wp.com/latex.php?latex=%7BN%7D&bg=ffffff&fg=000000&s=0&c=20201002)
do
not have a factor comparable to
![{\sqrt{N}}](https://s0.wp.com/latex.php?latex=%7B%5Csqrt%7BN%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
. (Quick proof: by the
Hardy–Ramanujan law, a typical number of size
![{N}](https://s0.wp.com/latex.php?latex=%7BN%7D&bg=ffffff&fg=000000&s=0&c=20201002)
or of size
![{\sqrt{N}}](https://s0.wp.com/latex.php?latex=%7B%5Csqrt%7BN%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
has
![{(1+o(1)) \log\log N}](https://s0.wp.com/latex.php?latex=%7B%281%2Bo%281%29%29+%5Clog%5Clog+N%7D&bg=ffffff&fg=000000&s=0&c=20201002)
factors, hence typically a number of size
![{N}](https://s0.wp.com/latex.php?latex=%7BN%7D&bg=ffffff&fg=000000&s=0&c=20201002)
will not factor into two factors of size
![{\sqrt{N}}](https://s0.wp.com/latex.php?latex=%7B%5Csqrt%7BN%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
.) So the above strategy cannot work for
![{k=3}](https://s0.wp.com/latex.php?latex=%7Bk%3D3%7D&bg=ffffff&fg=000000&s=0&c=20201002)
.
However, the situation changes for larger
. For instance, for
, we can try the same strategy with the ansatz
![\displaystyle \mathbf{n}_1 = \mathbf{d}_{12} \mathbf{d}_{13} \mathbf{d}_{14}; \quad \mathbf{n}_2 = \mathbf{d}_{12} \mathbf{d}_{23} \mathbf{d}_{24}; \quad \mathbf{n}_3 = \mathbf{d}_{13} \mathbf{d}_{23} \mathbf{d}_{34}; \quad \mathbf{n}_4 = \mathbf{d}_{14} \mathbf{d}_{24} \mathbf{d}_{34}.](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathbf%7Bn%7D_1+%3D+%5Cmathbf%7Bd%7D_%7B12%7D+%5Cmathbf%7Bd%7D_%7B13%7D+%5Cmathbf%7Bd%7D_%7B14%7D%3B+%5Cquad+%5Cmathbf%7Bn%7D_2+%3D+%5Cmathbf%7Bd%7D_%7B12%7D+%5Cmathbf%7Bd%7D_%7B23%7D+%5Cmathbf%7Bd%7D_%7B24%7D%3B+%5Cquad+%5Cmathbf%7Bn%7D_3+%3D+%5Cmathbf%7Bd%7D_%7B13%7D+%5Cmathbf%7Bd%7D_%7B23%7D+%5Cmathbf%7Bd%7D_%7B34%7D%3B+%5Cquad+%5Cmathbf%7Bn%7D_4+%3D+%5Cmathbf%7Bd%7D_%7B14%7D+%5Cmathbf%7Bd%7D_%7B24%7D+%5Cmathbf%7Bd%7D_%7B34%7D.&bg=ffffff&fg=000000&s=0&c=20201002)
Whereas before there were three (approximate) equations constraining three unknowns, now we would have four equations and six unknowns, and so we no longer have strong constraints on any of the
![{\mathbf{d}_{ij}}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bd%7D_%7Bij%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
. So in principle we now have a chance to find a suitable random choice of the
![{\mathbf{d}_{ij}}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bd%7D_%7Bij%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
. The most significant remaining obstacle is the Hardy–Ramanujan law: since the
![{\mathbf{n}_i}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bn%7D_i%7D&bg=ffffff&fg=000000&s=0&c=20201002)
typically have
![{(1+o(1))\log\log N}](https://s0.wp.com/latex.php?latex=%7B%281%2Bo%281%29%29%5Clog%5Clog+N%7D&bg=ffffff&fg=000000&s=0&c=20201002)
prime factors, it is natural in this
![{k=4}](https://s0.wp.com/latex.php?latex=%7Bk%3D4%7D&bg=ffffff&fg=000000&s=0&c=20201002)
case to choose each
![{\mathbf{d}_{ij}}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bd%7D_%7Bij%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
to have
![{(\frac{1}{3}+o(1)) \log\log N}](https://s0.wp.com/latex.php?latex=%7B%28%5Cfrac%7B1%7D%7B3%7D%2Bo%281%29%29+%5Clog%5Clog+N%7D&bg=ffffff&fg=000000&s=0&c=20201002)
prime factors. As it turns out, if one does this (basically by requiring each prime
![{p \leq N^{\varepsilon^2}}](https://s0.wp.com/latex.php?latex=%7Bp+%5Cleq+N%5E%7B%5Cvarepsilon%5E2%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
to divide
![{\mathbf{d}_{ij}}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bd%7D_%7Bij%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
with an independent probability of about
![{\frac{1}{3p}}](https://s0.wp.com/latex.php?latex=%7B%5Cfrac%7B1%7D%7B3p%7D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
, for some small
![{\varepsilon>0}](https://s0.wp.com/latex.php?latex=%7B%5Cvarepsilon%3E0%7D&bg=ffffff&fg=000000&s=0&c=20201002)
, and then also adding in one large prime to bring the magnitude of the
![{\mathbf{n}_i}](https://s0.wp.com/latex.php?latex=%7B%5Cmathbf%7Bn%7D_i%7D&bg=ffffff&fg=000000&s=0&c=20201002)
to be comparable to
![{N}](https://s0.wp.com/latex.php?latex=%7BN%7D&bg=ffffff&fg=000000&s=0&c=20201002)
), the calculations all work out, and one obtains the claimed result.
24 comments
Comments feed for this article
20 May, 2024 at 7:30 pm
Anonymous
Bravo!
20 May, 2024 at 7:53 pm
domotorp
See also https://arxiv.org/abs/2405.12088 which just appeared on arXiv.
20 May, 2024 at 8:08 pm
Terence Tao
Wow, that is quite a coincidence in timing! It seems the papers, while very adjacent in topic, do not actually overlap, but I will certainly update my paper to reference theirs.
21 May, 2024 at 9:04 am
Anonymous
That’s certainly amazing.
21 May, 2024 at 3:56 pm
Anonymous
Why the case of odd 𝑘 ≥ 5? see above
22 May, 2024 at 9:58 am
Terence Tao
I am not sure exactly what the thrust of your question is, but one can get significantly stronger upper bounds in the even case because one can exploit the birthday paradox: if one can find two separate
-tuples in
whose products have the same square-free part, then the product of the entire
-tuple will be a square. One can use this trick to generate even tuples that multiply to a square, but not odd tuples. Similarly, it is easier to generate strong lower bounds in the odd case than in the even case, because the set of numbers that have an odd number of prime factors in a given set
of primes, will necessarily have all odd products being a non-square, and all known counterexamples are based on this construction with a suitably optimized choice of
.
23 May, 2024 at 3:19 am
Will Sawin
Lovely!
If one were to make the upper bound on the density obtained by this method explicit, it would go to 1 with k. Indeed it couldn’t possibly be higher than 1-1/k since we need to lower bound the probability that a k-tuple of random variables lies in A based only on information in the marginal distribution, requiring us to use the union bound, which loses at least 1 minus the density for each element of the tuple.
Might it be possible to prove a bound uniform in k at least 5 by some modification of this method? It seems tricky as one would have to prove the events n_i in A approximately independent in some sense. But actually I’m not sure that this is the main obstacle – it’s possible the current bounds from an explicit version of your argument go to 1 significantly faster than this.
23 May, 2024 at 9:40 am
Terence Tao
It seems one can get a lower bound on the leading constant that is uniform in
by leveraging the even
theory, which among other things tells us that any set of positive density will contain
distinct elements multiplying to a square if
is fixed and even. So then if
is odd, and
is a subset of
that has density close to
, then one can first locate a tuple of five elements multiplying to a square, delete those elements, and then locate a tuple of
(which is an even number that is at least 4) elements that multiply to a square in the remaining set. (In the notation of the paper, this argument shows that
for any fixed
.) I’ll add this as a remark to the paper.
25 May, 2024 at 12:17 am
Csaba Sandor
Let
be a positive integer. Then
. Let
be a largest subset of
that does not contain
distinct elements whose product is a square. It is known that
. Then one can locate elements
,
multiplying to a square. Then
is a set that does not contain
distinct elements whose product is a square.
25 May, 2024 at 7:06 am
Terence Tao
Nice! So now the monotonicity of
for odd
is settled.
3 June, 2024 at 2:27 am
Anonymous
can you add it to your article (with ack. for Sandor of course)?
3 June, 2024 at 2:42 am
Anonymous
my bad, v2 already is there…
25 May, 2024 at 7:31 am
Terence Tao
One way to think about this phenomenon is that the set
is not an “irreducible” set in some arithmetic geometry sense, but instead has multiple interesting “components”. In my paper I rely more or less exclusively on the component which has the parameterization
for some natural numbers
with
. But there are other components as well; for instance one can retain this sort of parameterization just for
, but have an unrelated parameterization
,
for the final two components; this is related to the monotonicity of
for odd
discussed previously. It is not clear a priori which components give the strongest bounds on
(and perhaps the best bounds could even come from a synergy between multiple components, rather than just taking the best bound provided by a single component).
25 May, 2024 at 8:22 am
Terence Tao
As an experiment, I asked ChatGPT to provide Python code to compute the function
, defined as the size of the largest subset of
with no odd number of them multiplying to a square. This is a lower bound for all the
for odd
; the quantity
is also the minimal size of
where
ranges over
-valued completely multiplicative functions. As it turned out the code ran flawlessly (other than I had to figure out install the sympy package, and how to print the results), and only took me a few minutes to complete: https://chatgpt.com/share/e021a5fb-5040-427b-a1a8-260fb31eeb08 . On consulting the OEIS, I found that the sequence
already appears as https://oeis.org/A360659 (which also provided confirmation of the correctness of the GPT-provided code, which I also spot-checked with small values of
), although
is not, but I just submitted it to the OEIS. (I haven’t tried the analogous exercise with the
, which are harder to compute for
, but presumably one could get GPT to produce some algorithm that could produce enough entries to check the OEIS.)
UPDATE: F(N) is now at https://oeis.org/A373114
25 May, 2024 at 9:55 am
Terence Tao
Indeed, ChatGPT could compute
by brute force for
up to 10 in less than a minute: https://chatgpt.com/share/79ab37e7-d14d-4ae7-96d6-a5794a0a9581 . I could verify and extend the sequence by hand to
and it does not appear to be in the OEIS; I will add it after the sequence
is approved (this is currently in process). [
and
already appear in the OEIS as https://oeis.org/A028391 and https://oeis.org/A013928 respectively.]
UPDATE:
is now at https://oeis.org/A372306.
is at https://oeis.org/A373119,
is at https://oeis.org/A373178, and
is at https://oeis.org/A373195.
25 May, 2024 at 3:55 pm
Anonymous
has the oeis led to discoveries?
26 May, 2024 at 3:57 pm
Terence Tao
There are over 10,000 research papers that cite the OEIS, so I presume some non-trivial fraction of these found it useful.
30 May, 2024 at 1:58 pm
Anonymous
Are there similar results for representations of cubes?
[Yes; see the paper https://arxiv.org/abs/2405.12088 referenced in a previous comment -T.]
9 June, 2024 at 3:57 am
Anonymous
Is it possible to show that the sequence
is monotonic?
14 June, 2024 at 2:41 pm
Anonymous
Yes.
14 June, 2024 at 3:16 pm
Terence Tao
The
are known to equal 1 for even
, and are at most
for odd
, so the sequence is not monotonic over the full natual numbers; however they are monotonic non-decreasing for odd
(see the comment of Sandor here).
19 June, 2024 at 8:52 pm
Anonymous
Out of curiosity, how much time have you (Terry) spend browsing erdosproblems.com? I have spent some time clicking the random button.