Questions tagged [additive-combinatorics]
Questions on the subject additive combinatorics, also known as arithmetic combinatorics, such as questions on: additive bases, sum sets, inverse sum set theorems, sets with small doubling, Sidon sets, Szemerédi's theorem and its ramifications, Gowers uniformity norms, etc. Often combined with the top-level tags nt.number-theory or co.combinatorics. Some additional tags are available for further specialization, including the tags sumsets and sidon-sets.
206
questions with no upvoted or accepted answers
26
votes
0
answers
899
views
Which sets of roots of unity give a polynomial with nonnegative coefficients?
The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...
13
votes
0
answers
460
views
Correlation of Fourier transforms of characteristic functions
Let $A$ and $B$ ($A\subset B$) be subsets of a finite abelian group $G$. (For the sake of argument, you can take $G$ to be $\mathbb{Z}/p\mathbb{Z}$ for large $p$, say.) Write $1_S$ for the ...
12
votes
0
answers
193
views
What is the "right" notion of exponentiation in $\beta \mathbb N$?
The Stone–Čech compactification $\beta \mathbb N$ of the positive integers has extensive applications in combinatorial number theory.
A feature of $\beta \mathbb N$ that makes these applications ...
11
votes
0
answers
159
views
Bijections $\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ with vanishing local means
This is just a summer-time curiosity arisen after a recent question by Dominic van der Zypen.
For a finite subset $S$ of $\mathbb{Z}\times\mathbb{Z}$ and a function $f$ on $\mathbb{Z}\times\mathbb{...
11
votes
0
answers
523
views
Cyclic and prime factorizations of finite groups
A tuple $(A_1,\dots,A_n)$ of subsets of a finite group $G$ is called a factorization of $G$ if $G=A_1\cdots A_n$ and $|A_1|\cdots|A_n|=G$.
In Cryptology factorizations of groups are known as ...
11
votes
0
answers
813
views
Cliques in the Paley graph and a problem of Sarkozy
The following question is motivated by pure curiosity; it is not a part
of any research project and I do not have any applications. The question
comes as an interpolation between two notoriously ...
11
votes
0
answers
826
views
What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?
To construct gaps between primes which are marginally larger than average, Erdős and Rankin covered an interval $[1,y]$ with arithmetic progressions with prime differences. A nice short exposition is ...
10
votes
0
answers
172
views
Is almost every number the sum of two numbers with small radicals?
Define a set of numbers with small radicals (A341645 in OEIS) by
$$A_2=\{n\in\mathbb{N} \;|\; \text{rad}(n)^2\le n\}$$
The asymptotic density of $A_2\cap \{1,\dots N\}$ is $\sqrt{N}\times e^{2(1+o(1))\...
10
votes
0
answers
337
views
A formula for Frobenius number of certain numerical semigroups
The old formula for the Frobenius number of a numerical semigroup generated by two elements can be stated as follows: assume $\gcd\{a+1,b+1\}=1$, then the Frobenius number of $S= \left<a+1,b+1\...
9
votes
0
answers
263
views
If $A+A+A$ contains the extremes, does it contain the middle?
Let $b \ge 1$ and $A\subseteq [0,b]$ be a set of integers (all intervals will be of integers).
Write $hA := \underbrace{A + \ldots + A}_{h\text{ summands}} = \{ \sum_{i=1}^h a_i ~|~a_i \in A,\, \...
9
votes
0
answers
294
views
An abstract zero-sum problem
I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
9
votes
0
answers
422
views
A characterization of quadratics similar to an inverse sieve problem
Suppose $\mathscr{A} \subset \mathbb{N}$ enjoys for all large enough cutoffs $X$ the following properties:
$|\mathscr{A} \cap [1,X]| > \sqrt{X}/10$; and
the discriminant $\prod_{\alpha \neq \beta}|...
9
votes
0
answers
543
views
Partition regularity in the squares
A linear equation $c_1x_1 + \cdots + c_sx_s = 0$ is partition regular if for every partition of the natural numbers into colour classes $A_1, \ldots, A_r$, there is a solution to the equation in which ...
9
votes
0
answers
148
views
Why have most maximal cliques of Paley graphs odd size?
I ask this question mainly by curiosity.
See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$.
Is there an explanation ...
8
votes
0
answers
251
views
When does $A-A$ avoid $A$?
Chavez and Allawala recently used a statistical model to explain the empirical observation that the imaginary parts of the nontrivial zeros of the Riemann zeta function form a set $A\subseteq\mathbb{R}...
8
votes
0
answers
140
views
Minimum length of sequence such that every integer from 1 to n can be achieved as the sum of some contiguous subsequence
This question literally came to me in a fever dream last night, and it's frustrating me to no end. I'll try to explain it as best I can, but there may not be a satisfying answer; the best outcome ...
8
votes
0
answers
319
views
What is intuition behind sets with more sums than differences?
There exist finite sets $A$ in, say, $\mathbb{Z}$, such that $|A+A|>|A-A|$. The minimal such set contains 8 elements and consists of, say, 0, 2, 3, 4, 7, 11, 12, 14. How should I find such an ...
8
votes
0
answers
216
views
Sets of natural numbers which are almost closed under addition
I am interested in a classification of sets $A \subseteq \mathbb{N}$ such that for all $k \in A$, $d( A+k \cap \mathbb{N} \setminus A) = 0$ where $d$ is the asymptotic density and $A+k = \{n \in \...
8
votes
0
answers
299
views
A strong sum-product "for translates" in finite fields
In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...
8
votes
0
answers
207
views
Erdös-Fuchs Theorem for multivariate linear forms
Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$.
It is not very difficult to show that if $r(n) > 0$ ...
8
votes
0
answers
448
views
Small maximal sets with no 3-AP?
Everyone knows about the problem of finding the largest set in 1,2,...,N which contains no arithmetic progression of length 3.....what happens if we look at the set which is the
smallest maximal ...
7
votes
0
answers
154
views
Circles with many points from an additive subgroup of $\mathbb{R}^2.$
Given a point set in the plane, defined by three distinct, non-zero vectors $v_1,v_2,v_3\in \mathbb{R}^2.$
$$L_n=\{a_1v_1+a_2v_2+a_3v_3 | a_1,a_2,a_3\in\{0,1,\ldots,n\}\}$$ What is the largest ...
7
votes
0
answers
189
views
Primitive recursive bounds for the the Gallai-Witt theorem
Let me first recall some facts:
By the work of Gowers, the Van der Waerden numbers belong to class $\mathcal{E}^3$ of the Grzegorczyk hierarchy
By the work of Shelah, the Hales-Jewett numbers belong ...
7
votes
0
answers
116
views
A conjecture on circular permutations of n elements in an abelian group of odd order
In 2013 I formulated the following conjecture in additive combinatorics.
Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is ...
7
votes
0
answers
261
views
Is every integer $n>1$ the sum of two squares and two central binomial coefficients?
Those integers $\binom{2n}n\ (n=0,1,2,\ldots)$ are called central binomial coefficients. By Stirling's formula,
$$\binom{2n}n\sim \frac{4^n}{\sqrt{n\pi}}\ \ \ \ (n\to+\infty).$$
Of course, the ...
7
votes
0
answers
239
views
Distribution of trivial subset sums
Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
7
votes
0
answers
311
views
Other applications of the 'increment' approach
I would like to hear about other instances of the so-called 'increments' approach, first used by Roth to prove that a subset of $\mathbb{N}$ of positive upper density contained infinitely many ...
7
votes
0
answers
719
views
Largest set of integers without 3-term arithmetic progressions mod $n$
I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b \...
6
votes
0
answers
491
views
At most two elements give 1 to n
Fix a positive integer $m$. Let $n$ ( $= n(m)$) be the largest positive integer for which there exists some subset $\{a_1,\ldots,a_m\} \subseteq \{1,2,\ldots,n\}$ of $m$ positive integers between $1$ ...
6
votes
0
answers
171
views
Plausible ways to discover higher order fourier analysis
Szemeredi's Theorem is a difficult theorem that falls into the category of not obviously foundational or widely applicable in itself but where the search for proofs have led to a number of ...
6
votes
0
answers
145
views
A variant of the capset problem
Let $p > 2$ be a prime of bounded size.
Suppose $A$ is a subset of $G = \mathbf{F}_p^n$ with only degenerate solutions to
$$x + y = 2a,\\
x+z = 2b,\\
y + z = 2c,$$
where a solution is considered ...
6
votes
0
answers
145
views
When is $\{s_2-s_1,s_3-s_2,s_1-s_3\}\cap S$ non-empty for any $s_1,s_2,s_3\in S$?
A subset $S$ of an abelian group is a subgroup if and only if it is closed under taking differences; that is, the difference of any two elements of $S$ is in $S$. Suppose, however, that we only know ...
6
votes
0
answers
333
views
Legendre's three-square theorem and squared norm of integer matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $E_n$ be the set of integers which are the sum of $n$ squares. Let $F_n$ be the set of integers of the form $\Vert A \Vert^2$ with $A \in M_n(...
6
votes
0
answers
177
views
Growth in a vector space
I am interested in "growth" in finite vector spaces. I have been wondering about the veracity of the following statement:
Statement: For every $\varepsilon>0$ there exists $b\in\mathbb{Z}^+$ ...
6
votes
0
answers
153
views
Large cubes in sum/difference sets
If $A$ is a subset of an abelian group with $|A+A|\leq K|A|$ then one can show that $A$ contains a large cube of size depending on $K$. Here a cube is a set of the form
$$C=\{a_0+\sum_{i=1}^d e_ia_i:...
6
votes
0
answers
744
views
Expectation of Gowers norm
This was a problem that came up during a course on Analytic Combinatorics that I had taken this semester. Here's the problem:
Let $\mathbf{F}$ be the set of boolean functions, $f: \mathbb{F}_2^n \...
5
votes
0
answers
189
views
Is it true that the $\mathbb{F}_p$-rank of a linear combination of matrices is usually not smaller than its $\mathbb{Q}$-rank?
Consider fixed $3 \times 3$ integer matrices $A_1,A_2,A_3$ and the $\sim H^3$ linear combination matrices $A(\mathbf{h})=h_1A_1+h_2A_2+h_3A_3$ where $h_1,h_2,h_3$ are integers with $\vert h_i\vert \le ...
5
votes
0
answers
77
views
Maximum size of difference sets with a bounded number of prime divisors
Call a subset $S\subset \mathbb{Z}$ $r$-smooth if the difference set $S-S$ contains numbers whose prime divisors lie in a set $P$ of distinct primes with $|P|=r$. Let $f(r)$ be the maximum size of any ...
5
votes
0
answers
191
views
Showing that Fourier pseudorandomness is insufficient for $k=4$ case (four arithmetic progressions)
I wish to show that the Fourier pseudorandomness is insufficient to count the number of 4-term arithmetic progression.
Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a subset of a cyclic group $\mathbb{Z}/...
5
votes
0
answers
197
views
Ramsey Numbers for Integers
Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...
5
votes
0
answers
114
views
Low-rank approximation over finite fields
Consider the finite field $\mathbb{F}_p$ with prime $p$. Let $I=\{ 0,1,2,...,|I|-1 \}\subset \mathbb{F}_p$ be an "interval".
What can be the largest size $|I|$, such that there exists a $2\times 2$ ...
5
votes
0
answers
171
views
Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles
Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...
5
votes
0
answers
332
views
Lower bound for some sums of roots of unity
Let $n$ be a positive integer (assume $n$ is prime for simplicity), and let $x_k = \pm1$, for $k = 0,1,2,..., n-1$. Let $\rho$ be an $n-$th primitive root of unity, I am interested in a lower bound ...
5
votes
0
answers
195
views
Is every integer $n>1$ the sum of two triangular numbers and two powers of $5$?
Recall that the triangular numbers are those integers
$$T_n=n(n+1)/2\ \ \ (n=0,1,2,\ldots).$$
In 1796 Gauss proved that each $n\in\mathbb N=\{0,1,2,\ldots\}$ is the sum of three triangular numbers, ...
5
votes
0
answers
113
views
$m$-thick sets with small $n$-fold sumsets in finite cyclic groups
Problem. Is it true that for every positive integers $n,m$ there exists a subset $A_{n,m}$ of a finite cyclic group $G$ having the following two properties:
$(\Sigma_n)$ the $n$-fold sum $A_{n,m}^{+...
5
votes
0
answers
831
views
Increasing sequences in polynomial progressions modulo p
In a random permutation on $n$ elements one expects the largest increasing and decreasing sequences to have size $(2+o(1))\sqrt{n}$. Is it known if this same property holds in sequences given by ...
5
votes
0
answers
153
views
Negative values of cosine sums
Consider real numbers $x_1, \dots, x_M$ such that
$$\sum_{i=1}^{M} \frac{\cos(x_i t^2)}{e^{(x_it)^2}} \le -\frac{1}{2}, $$
for all $L< t <L^A,$ where L is a large number.
What lower bound ...
5
votes
0
answers
79
views
Some questions about the Lévy monoid of certain densities
Let $\bf H$ be a set, $f: \mathcal P({\bf H}) \rightharpoonup \bf R$ a partial function, and $\mathcal{D}$ the domain of $f$.
Next, denote by $\mathcal M(f)$ the set of all (total) functions $\theta: ...
5
votes
0
answers
239
views
The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$
Let $N=\{1,2,\ldots ,n\},n>1$. We wish to construct a set $A\subseteq N$ with the property:
The sum of all the elements of every non empty subset of $A$ is not a
multiple of $n$.
Question: ...
5
votes
0
answers
247
views
"Pseudo-random" subsets of additive bases
We say that a subset $B \subset \mathbb{N}$ is an (asymptotic) additive basis of order $k$ if the set $kB = B + \cdots + B = \mathbb{N} \setminus C$, where $C$ is a finite set of positive integers. ...