ABSTRACT (original article): Let
SPP(n)
be the set
{(|A+A|,|AA|):A⊆,|A|=n}
of sum-product pairs, where
A+A
is the sumset
{a+b:a,b∈A}
and
AA
is the product set
{ab:a,b∈A}.
We construct a dataset consisting of 1162868 sets whose sum-product pairs are at least 84% of
SPP(n)
for each
n≤32
. Notably, we do **not** see evidence in favor of Erdős’s Sum-Product Conjecture in our dataset. For
n≤6
, we prove the exact value of
SPP(n)
. We include a number of conjectures, open problems, and observations motivated by this dataset, a large number of color visualizations. CITATION (original article): Kevin O’Bryant (2024), Visualizing the Sum-Product Conjecture, arXiv:2411.08139. https://doi.org/10.48550/arXiv.2411.08139
The sumset
A+A
of a set of
n
integers is the set
{a+b:a∈A}
, and the product set
AA
is
{ab:a,b∈A}
. By elementary combintorics, both
|A+A|
and
|AA|
are between
2n-1
and
n(n+1)/2
. One of the most worked-upon conjectures in additive number theory is Erdös’s Sum-Product Conjecture: For all
ϵ>0
, if
n
is large enough, then at least one of
|A+A|,|AA|
is at least
2-ϵ
n
.
In “Visualizing the Sum-Product Conjecture” I computed as many sum-product pairs
(|A+A|,|AA|)
for each
n=|A|
up to 32 as I could manage, with
A
constrained to the positive integers. This dataset is certainly incomplete but contains at least 7/8-ths of the conceivable sum-product pairs for each
n
.
One can certainly stare at the unnormalized pairs, but the sum-product conjecture just concerns pairs that are extremely close to (1,1), the lower-left corner of our picture.
A more interesting picture is to normalize with a base-
n
logarithm, i.e., the pairs
(
log
n
|A+A|,
log
n
|AA|)
. Now, the Sum-Product Conjecture says that as
n->∞
, the sum-product pairs must congregate along the northern or eastern edge of our picture. However, the pictures show that not only are the points not drifting north and east, but the lower envelope is actually moving south and west! This suggests that the Sum-Product Conjecture may be false (or that
n=32
is too small).
​
The combinatorial upper and lower bounds are approximately
2
n
/2
and
2n
, and the effect of these factors of 2 shows up in these images as stretching the points away from the center as
n
increases. So perhaps this explains the drift south and west for small
n
.
It is known that if the product set is too small, then the sumset must be extremely large, this region is labelled as SEZ on our pictures. Solymosi has proved that a particular triangle cannot contain any limit points in its interior, and this triangle is marked in our pictures as the “Solymosi Void”.
To compensate for those factors of 2 in the upper and lower bounds, we can normalize better. We can find find linear functions
ϕ
1
,
ϕ
2
,
ϕ
3
so that
log
n
(2n-1)+
ϕ
1
(2n-1)==1,
log
n
n(n+1)
2
+
ϕ
1
n(n+1)
2
==2​​
log
n
ϕ
2
(2n-1)==1,
log
n
ϕ
2
n(n+1)
2
==2​​
ϕ
3
(
log
n
(2n-1))==1,
ϕ
3
log
n
n(n+1)
2
==2,
We show all of these normalizations in our images, and they all show sum-product pairs getting further south and further west, with more drift as
n
increases.
Conjecture: For every set
A
of positive integers,
A+A*AA>=
1
2
A
3
|
.
This conjecture is supported by our data, does not imply Erdös’s Sum-Product Conjecture, and seems to old for every set
A
, not merely as
|A|->∞
.
In[]:=
Get[FileNameJoin[{NotebookDirectory[],"SP.mdata"}]];​​SP[5]
Out[]=
{{9,14},{15,9},{12,12},{15,12},{13,12},{11,15},{14,12},{10,14},{15,11},{12,14},{15,14},{13,14},{14,14},{11,12},{10,15},{12,13},{12,15},{15,13},{15,15},{13,13},{13,15},{11,14},{14,13},{14,15},{15,10},{10,12},{9,15}}
Normalizing Functions
In[]:=
none[k_,x_]:=
2x+4-7k+
2
k
2-3k+
2
k
;​​K1[k_,x_]:=N
4-7k+
2
k
2-3k+
2
k
+
-1
Binomial[k-1,2]
(2k-1)Logk,
1
2
k(1+k)-
k(1+k)
2
Log[k,2k-1]+
-1
Binomial[k-1,2]
Logk,
4k-2
1+k
x+Log[k,x];​​L[n_,x_]:=N[Log[n,x]];​​K2[n_,x_]:=NLogn,
2n
n-2
x-
3
2
n
n-2
;​​K3[n_,x_]:=N
Log[n]
Log[n(1+n)]-Log[-2+4n]
Log[n,x]+1+
Log[-1+2n]
Log[-2+4n]-Log[n+
2
n
]
;​​​​normy[0]=none;​​normy[1]=L;​​normy[2]=K1;​​normy[3]=K2;​​normy[4]=K3;​​​​fromstring["none"]=0;​​fromstring["logarithm"]=1;​​fromstring["log + linear"]=2;​​fromstring["log( linear )"]=3;​​fromstring["linear( log )"]=4;
In[]:=
SolymosiVoid={Graphics[{LightPink,Opacity[0.5],Polygon[{{1,1},{1,2},{3/2,1},{1,1}}]}],​​Graphics[{Dashed,Red,Line[{{1,1},{1,2},{3/2,1},{1,1}}]}],​​Graphics[Rotate[Text[Style["Solymosi Void",Medium],{1.35,1.2}],ArcTan[-2]]]};
In[]:=
SEZ[k_]:=Module[{corner=If[k==3,{1.6,1.6},N[{K1[k,k(k+1)/2-Max[3/4,(1-1/k)]],K1[k,3k-3-Max[3/4,(1-1/k)]]}]]},{Graphics[{Black,Text["SEZ ",corner,{1,1}],RGBColor[0,0.05,0],Opacity[0.1],Rectangle[{1,1},corner]}]}];​​SEZ[normalizer_,k_]:=Module[{corner=If[k==3,{1.6,1.6},N[{normalizer[k,k(k+1)/2-Max[3/4,(1-1/k)]],normalizer[k,3k-3-Max[3/4,(1-1/k)]]}]],​​start=normalizer[k,2k-1]*{1,1}},{Graphics[{Black,Text["SEZ ",corner,{1,1}],RGBColor[0,0.05,0],Opacity[0.1],Rectangle[start,corner]}]}];​​​​background=ListPlot[{},AspectRatio->1,PlotStyle->Medium,PlotRange->{{0.95,2.05},{0.95,2.05}},Ticks->{Range[1,2,0.1],Range[1,2,0.1]}];​​box=Graphics[{LightBlue,Line[{{1,1},{1,2},{2,2},{2,1},{1,1}}]}];​​sidelabels=Graphics[{Text[Style["Geometric Progressions",Bold,Large],{1.5,0.88}],​​Text[Style["Multiplicative Sidon Sets",Bold,Large],{1.5,2.05}],​​Rotate[Text[Style["Arithmetic Progressions",Bold,Large],{0.85,1.5}],Pi/2,{0.85,1.5}],Rotate[Text[Style["Sidon Sets",Bold,Large],{2.05,1.5}],-Pi/2,{2.05,1.5}]​​}];
In[]:=
Clear[image];​​image[k_,n_Integer]:=image[k,n]=​​Module{pts,pic,sides},​​pts=Map[normy[k][n,#]&,SP[n]];​​pic=ListPlotpts,AspectRatio->1,PlotStyle->ColorData["Rainbow"]
n-3
29
,PointSize
0.06
Log[1+Length[pts]]
,​​PlotRange->{{0.80,2.10},{0.80,2.10}};​​Show[​​background,If[k!=0,SolymosiVoid,Graphics[]],​​SEZ[normy[k],n],​​box,​​pic,sidelabels,​​PlotRange->{{0.80,2.10},{0.80,2.10}},​​ImageSize->500];
In[]:=
image[k_,33]:=image[k,33]=​​Module{pts,pic,onepic,maxn=32},​​Do[pts[n]=Map[normy[k][n,#]&,SP[n]],{n,3,maxn}];​​Doonepic[n]=ListPlotpts[n],AspectRatio->1,PlotStyle->ColorData["Rainbow"]
n-3
29
,PointSize[Small],{n,3,maxn};​​pic=Table[onepic[n],{n,maxn,3,-1}];​​Show[​​background,If[k>0,SolymosiVoid,Graphics[]],​​box,​​pic,sidelabels,​​PlotRange->{{0.80,2.10},{0.80,2.10}},Ticks->{{{1,"1.0"},{1.1`,"1.1"},{1.2`,"1.2"},{1.3`,"1.3"},{1.4`,"1.4"},{1.5`,"1.5"},{1.6`,"1.6"},{1.7`,"1.7"},{1.8`,"1.8"},{1.9,"1.9"},{2.`,"2.0"}},{{1,"1.0"},{1.1`,"1.1"},{1.2`,"1.2"},{1.3`,"1.3"},{1.4`,"1.4"},{1.5`,"1.5"},{1.6`,"1.6"},{1.7`,"1.7"},{1.8`,"1.8"},{1.9,"1.9"},{2.`,"2.0"}}},​​ImageSize->500]
In[]:=
Monitor[Do[image[k,n],{k,0,4},{n,3,33}],{k,n}]
Manipulate[image[fromstring[k],n],{{k,"none","Normalization"},{"none","logarithm","log + linear","log( linear )","linear( log )"}},{{n,16,"|A|"},3,33,1},SaveDefinitions->True]
Out[]=

CITE THIS NOTEBOOK

Visualizing the sum-product conjecture​
by Kevin O’Bryant​
Wolfram Community, STAFF PICKS, July 5, 2025
​https://community.wolfram.com/groups/-/m/t/3492137