By Kevin O'Bryant
Department of Mathematics, City University of New York,
The College of Staten Island and The Graduate Center, NY, USA
Abstract
Let \(SPP(n)\) be the set \(\left\{\big(|A+A|,|A A|\big) : A\subseteq {\mathbb N}, |A|=n\right\}\) of sum-product pairs, where \(A+A\) is the sumset \(\{a+b : a,b\in A\}\) and \(A A\) is the product set \(\{ab:a,b\in A\}\).
We construct a dataset consisting of 1,162,868 sets whose sum-product pairs are at least 84% of \(SPP(n)\) for each \(n\le 32\).
Notably, we do not see evidence in favor of Erdős's Sum-Product Conjecture in our dataset. For \(n\le 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 copied to clipboard!
Key Finding
Image source: compressedpics/pics_everything_33L.pdf in the paper.
The pairs (log|A+A|/log|A|, log|AA|/ log|A|) for 1,162,868 sets of positive integers. Points from larger sets are colored more red, from smaller sets more purple. The larger sets were used first, so that beneath the purple/blue/green points are hidden red points. The yellow-orange-red progression of points along the lower edge suggest that the Sum-Product Conjecture --- which states that in the limit all points will be along the north and east edges --- is false, or at least that n=32 is too small for the effect to begin.
Paper
The full paper "Visualizing the Sum-Product Conjecture" is available on arXiv:
Read Paper on arXiv
OEIS Sequences
The following integer sequences from the Online Encyclopedia of Integer Sequences (OEIS) are referenced in the paper:
The number of distinct sum-product pairs (|A+A|,|AA|) that can be realized by sets A of n positive integers.
A378609 - Number of types of addition tables of order n
The number of n × n symmetric matrices whose values cover an initial interval of positive integers and for which there is a set of positive integers with corresponding addition structure.
Key Visualizations
The following visualizations represent different normalizations of the sum-product pairs in our dataset:
K-Normalization
Normalization using \(K_n(x) = \log_n(x) + m_n x + b_n\)
Sets giving all sum-product pairs that arise from sets of positive integers with diameter at most 31. Generated by considering all shifts of all subsets of [32].
These files define functions that provide structured access to the datasets:
SPP.mdata
Defines a function SPP[n], where n can be any positive integer up to 36. SPP[n] is an Association (Mathematica's Dictionary) whose keys are {sumset_size, productset_size} and whose values are sets of positive integers.
Each line contains one set of positive integers in the format:
{a_1, a_2, ..., a_n}
For example:
{1, 2, 3, 4, 6, 8, 9, 12}
The sumset and product set sizes are not included in the text files, but can be computed directly from each set.
Mathematica Format (.mdata)
The data is stored as a collection of Mathematica dictionaries that can be loaded using:
Get["path/to/file.mdata"]
The structure consists of dictionaries named SPP[n] where n is the set size. For each SPP[n]:
The keys are pairs {x, y} representing |A+A| = x and |AA| = y
The values are sets of n positive integers whose sumset has x elements and whose product set has y elements
For example, SPP[5][{12, 13}] would give you a set of 5 positive integers with 12 sums and 13 products.
Usage Examples
Mathematica
(* Load the data *)
Get["all_sets.mdata"]; (* This loads all SPP[n] dictionaries *)
(* Access a specific set with known sum-product pair *)
(* Example: Get a set of size 6 with 15 sums and 15 products *)
exampleSet = SPP[6][{15, 15}];
(* Get all sum-product pairs for sets of size 10 *)
pairs10 = Keys[SPP[10]];
(* Extract all sets of size 10 *)
sets10 = Values[SPP[10]];
(* Find all sets with a specific property *)
FindSetsWithProperty[n_, property_] :=
Select[KeyValueMap[{#1, #2} &, SPP[n]], property[#] &];
(* Example: Find sets of size 7 whose maximum element is less than 50 *)
smallSets = FindSetsWithProperty[7, Function[{pair, set}, Max[set] < 50]];
(* Plot normalized sum-product pairs for n = 20 *)
n = 20;
pairs = Keys[SPP[n]];
ListPlot[pairs, PlotRange -> All,
AxesLabel -> {"|A+A|", "|AA|"},
PlotLabel -> "Sum-Product Pairs for n = " <> ToString[n]]
Python
import numpy as np
import matplotlib.pyplot as plt
# Function to compute sumset A+A
def sumset(A):
sums = set()
for a in A:
for b in A:
sums.add(a + b)
return sums
# Function to compute product set AA
def productset(A):
products = set()
for a in A:
for b in A:
products.add(a * b)
return products
# Load the data (sets only)
def load_data(filename):
sets = []
with open(filename, 'r') as f:
for line in f:
# Parse the set from the line, removing braces and splitting by commas
elements = [int(x) for x in line.strip().strip('{}').split(',')]
sets.append(elements)
return sets
# Compute sum-product pairs for a list of sets
def compute_sum_product_pairs(sets):
result = []
for s in sets:
sums = sumset(s)
products = productset(s)
result.append((len(s), len(sums), len(products), s))
return result
# Example usage
sets = load_data('all_sets.txt')
# Filter sets of a specific size
def get_sets_of_size(sets, n):
return [s for s in sets if len(s) == n]
# Compute and plot sum-product pairs for sets of size n
def plot_pairs(sets, n):
sets_n = get_sets_of_size(sets, n)
data = compute_sum_product_pairs(sets_n)
sum_sizes = [entry[1] for entry in data]
prod_sizes = [entry[2] for entry in data]
plt.figure(figsize=(10, 8))
plt.scatter(sum_sizes, prod_sizes, alpha=0.5)
plt.xlabel('|A+A|')
plt.ylabel('|AA|')
plt.title(f'Sum-Product Pairs for n = {n}')
plt.grid(True, alpha=0.3)
plt.savefig(f'spp_{n}.png')
plt.show()
# Example: Plot for n = 15
plot_pairs(sets, 15)
Contact
For questions, suggestions, or to contribute additional sets to the dataset, please contact:
Kevin O'Bryant
Email: kevin.obryant@csi.cuny.edu
Department of Mathematics
City University of New York
The College of Staten Island and The Graduate Center
