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.
665
questions
5
votes
1
answer
482
views
How large can a non-sumset be?
The theory of sumsets $A+B$ where $A$ and $B$ are finite subsets of an additive group $Z$ is extensively studied in additive combinatorics: finding long arithmetic progressions inside them, finding ...
- 6,608
5
votes
1
answer
452
views
Questions on 'Improved bounds for the sunflower lemma'
I have been reading 'Improved bounds for the sunflower lemma' by Alweiss, Lovett, Wu and Zhang (Ann. of Math., Vol. 194(3), 2021), and have some gaps in my understanding of the paper. They are as ...
user469866
5
votes
2
answers
253
views
The number of co-circular four tuples
Let $A,B ⊂ \mathbb{R}$ such that $|A| = |B| = n$. What is the best-known upper bound on the number of four-tuples in $A \times B$ where the four points are co-circular, they lie on the same circle?
- 389
5
votes
1
answer
806
views
Density of intersection with shifted sets
Given a subset $S$ of the positive integers $\mathbf{N}$, let $\mathrm{d}^\star(S)$ be its upper asymptotic density, that is,
$$
\mathrm{d}^\star(S)=\limsup_{n\to \infty}\frac{|S \cap [1,n]|}{n}.
$$
...
- 1,451
5
votes
1
answer
273
views
Element with unique representation in A+B
Let $A, B \subseteq \mathbb{Z}$ be finite subsets of the integers. Then there exists an element in $A+B$ with a unique representation as a sum of an element in $A$ and an element in $B$, namely $\max(...
- 83
5
votes
1
answer
316
views
Primitive recursive bounds for multidimensional polynomial vdW / HJ
In Shelah's paper 679, he proves primitive recursive bounds for the polynomial Hales-Jewett theorem and thus for the polynomial van der Waerden theorem.
How about for the multidimensional polynomial ...
- 383
5
votes
2
answers
242
views
Progressions in sumset or complement
Fix $\epsilon>0$.
For all large $N$, does there exist $A\subset [N]:=\{1,\dots,N\}$ such that both $A+A$ and $A^c:=[N]\setminus A$ lack arithmetic progressions of length $N^\epsilon$?
I am aware ...
- 3,413
5
votes
3
answers
682
views
How to prove the combinatorial identity $\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n}$ for $n\ge\ell\ge0$?
With the aid of the simple identity
\begin{equation*}
\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{k}}=2^n
\end{equation*}
in Item (1.79) on page 35 of the monograph
R. Sprugnoli, Riordan Array Proofs of ...
- 838
5
votes
1
answer
547
views
Additive energy of random sets
Given two random sets $A,B$ in a finite field (say $x\in A$ independently and with probability $1/2$), what is known about the additive energy $E(A,B)=|\{(a,a',b,b')\in A\times A\times B\times B: a+b=...
- 1,701
5
votes
1
answer
354
views
Is the generalized Erdős–Heilbronn problem true for finite cyclic groups?
The generalized Erdős–Heilbronn (GEH) theorem, which is proved by da Silva and Hamidoune in 1994, states that:
Theorem. If p is a prime and $X$ is a subset of $\mathbb{Z}_p$, then $|\hat{k}X| \geq \...
- 1,250
5
votes
1
answer
146
views
Beating trivial bound for $k$-AP-free sets in characteristic $k$
Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$.
Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...
- 3,413
5
votes
1
answer
344
views
Is every integer $\ge 312$ the sum of two integers with triangular divisors?
We say that a natural number $n$ has triangular divisors if it has at least one triplet of divisors $n = d_1d_2d_3$, $1 \le d_1 \le d_2 \le d_3$, such that $d_1,d_2$ and $d_3$ form the sides of a ...
- 4,638
5
votes
1
answer
176
views
Computational version of inverse sumset question
Let $p$ be prime and $\mathbb{F}_p$ the finite field with $p$ elements. Suppose we have a set $B\subseteq \mathbb{F}_p$ satisfying $|B|<p^{\alpha}$ for some $0<\alpha<1$ and there exists $A\...
user156885
5
votes
1
answer
160
views
Eccentricity in the number of representations for sets too large to be Sidon sets
Let $A=\{a_1<a_2<a_3<\dots< a_k\}\subset\{1,2,\dots,N\}$ be a set of integers. Let $r_A(n)=\#\{(a_i,a_j):a_i+a_j=n\}$ be the number of representations of $n$ as a sum of two elements from $...
- 278
5
votes
1
answer
288
views
Additive basis of order 2
Can we find $\alpha>1$ such that $u=(\lfloor n^\alpha\rfloor)_{n\geqslant0}$ is an additive basis of order $2$ (i.e. $\forall x\in\mathbb{N}, \exists(n,m)\in\mathbb{N}^2, x=u_n+u_m$) ?
Remark : ...
- 593
5
votes
1
answer
227
views
Unicity of additive, $(-1)$-homogeneous, and shift invariant probability measures on $\mathbf N^+$
Let $\mathcal D$ be the set of all (finitely) additive probability measures $\mu^\ast: \mathcal P(\mathbf N^+) \to [0,\infty[$ such that $\mu^\ast(k \cdot X + h) = \frac{1}{k} \mu^\ast(X)$ for all $X \...
- 9,636
5
votes
1
answer
632
views
Cauchy-Davenport strengthening?
Is the following statement, refining classical Cauchy-Davenport Theorem (that states that for sets $A$, $B$ of residues modulo prime $p$, $|A+B|\geq |A|+|B|-1$ provided that RHS does not exceed $p$) ...
- 103k
5
votes
1
answer
269
views
Expected number of coin flips before you see a $k$-term arithmetic progression of heads
Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...
- 4,832
5
votes
1
answer
274
views
How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?
First some
Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...
- 6,720
5
votes
2
answers
499
views
Anticoncentration of the convolution of two characteristic functions
Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A \...
- 706
5
votes
1
answer
931
views
Minimal polynomial of sums of roots of unity with constant term $\pm1$
Let prime $p$ and given $\zeta_p = e^{2\pi i/p}$. It is well-known that the minimal polynomial of $x = \zeta_p + \zeta_p^{p-1}$ has a constant term either $\pm 1$ and, for certain $p$, the sum of ...
- 12.1k
5
votes
1
answer
119
views
Maximum size of a critical set that sums to $n$
Say that a set $S \subset \mathbb Z^+$ can express $n$ if there is some way to add elements of $S$ (possibly more than once) to equal $n$. Call $S$ critical if moreover no proper subset of $S$ can ...
- 4,843
5
votes
1
answer
357
views
Sum-product estimate in finite fields
There is a paper by Bourgain, Katz and Tao
Bourgain, Jean; Katz, N.; Tao, Terence C., A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14, No. 1, 27-57 (2004). ZBL1145....
- 51
5
votes
3
answers
399
views
Request for reference for some proofs about Gowers' norm
For any map $f : \mathbb{F}_2^n \rightarrow \mathbb{C}$ we define its $d^{th}-$Gowers' Norm (for $1 \leq d \leq n$) as, $\|f\|_{U^d(\mathbb{F}_2^n)}^{2^d} = \mathbb{E}_{L : \mathbb{F}_2^d \rightarrow \...
- 2,146
5
votes
1
answer
469
views
Additivity of upper densities with respect to arithmetic progressions of integers
Let $\mathsf{d}^\star$ be the asymptotic upper density, defined on the power set of positive integers $\mathbf{N}^+$, so that
$$
\mathsf{d}^\star\colon \mathcal{P}(\mathbf{N}^+) \to\mathbf{R}\colon X\...
- 1,451
5
votes
1
answer
780
views
Balog-Szemeredi-Gowers with dilates of sets
All sets are assumed to be finite subsets of the integers.
The additive energy of two sets $E(A,B)$ is defined as the number of solutions to $a+b=a'+b'$ with $a,a'\in A$ and $b,b'\in B$. The well-...
- 6,608
5
votes
1
answer
381
views
Thin subbases for the primes?
Hi all,
My question concerns a general problem concern the Erdos-Turan conjecture on additive bases; that of finding thin subbases in a given basis. For a given $A \subset \mathbb{N}$, define $r_{A,h}...
- 25.5k
5
votes
1
answer
1k
views
A question on the singular series and singular integral in Hardy-Littlewood Circle Method
Given a set $A$ of positive integers, set $r_{A,h}(N)$ to be the number of $h$-tuples $(a_1, \cdots, a_h)$ such that $N = a_1 + \cdots + a_h$. Set $f(z) = \sum_{a \in A} z^a$. Then by Cauchy's Theorem ...
- 25.5k
5
votes
1
answer
265
views
Is there a short proof for the permutation invariance of this combinatorial map?
Consider a positive integer $n$ and integers $(c_i)_{1\le i \le 4}$, with $1 \le c_i \le n$. Conside the map:
$$f_n: (c_1,c_2,c_3,c_4) \mapsto \delta_{c_1,c_2}\delta_{c_3,c_4} - \# \{ |2n+1-2|x||, \ x ...
- 25.9k
5
votes
1
answer
372
views
Disjoint union of affine subspaces contains a larger affine subspace
I'd like to say that a large structured subset of the $n$-dimensional Boolean cube $\{0,1\}^n$ contains a non-trivial affine subspace. To be more specific, I want to prove/disprove that for some ...
- 211
5
votes
1
answer
254
views
Divisibility labeling on a boolean lattice and nonzero Euler totient
Let $B_n$ be the subset lattice of $\{1,2, \dots , n \}$, also called the boolean lattice of rank $n$.
A labeling $f: B_n \to \mathbb{N}_{\ge 1}$ is called acceptable if $\forall a,b \in B_n$:
...
- 25.9k
5
votes
2
answers
379
views
Ordered lattice point enumeration
I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.
Setup: Let $e_{...
- 547
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 ...
- 4,792
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. ...
- 141
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$ ...
- 51
5
votes
0
answers
173
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 ...
- 19.1k
5
votes
0
answers
336
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 ...
- 1,020
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, ...
- 14.5k
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}^{+...
- 40.9k
5
votes
0
answers
833
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 ...
- 383
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 ...
- 507
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: ...
- 9,636
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: ...
- 3,826
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. ...
- 25.5k
5
votes
0
answers
434
views
A question about Erdős thin bases
Let $B \subset \mathbb{N}$ be an additive basis of order $h$. Define $r_{B,h}(n)$ to be the number of ways $n$ can be written as a sum of $h$ elements of $B$. In particular, $B$ is a basis of order $h$...
- 25.5k
4
votes
1
answer
1k
views
a conjecture in sum-free sets
Let $ A $ be a set of non-zero integers. Then $A$ contains a sum-free subset $B$ of size $ |B|> \frac{|A|}{3} $ (a result of Erdős). It is conjectured that RHS can be improved to $\frac{|A|}{3} +...
- 2,076
4
votes
2
answers
504
views
Average involving the Euler phi function
Does
$$\frac{1}{N^2}\sum _{d=1}^N \log d \sum _{n=1}^{N/d} \frac{\phi(n)}{\log (dn)},$$
converges or not when $N$ goes to infinity?
- 43
4
votes
2
answers
529
views
Density version of the Erdos-Graham conjecture
In 2003 E. S. Croot [Ann. of Math. 157(2)(2003), 545-556] proved the Erdos-Graham Conjecture which states that if $\{2,3,\ldots\}$ is partitioned into finitely many subsets then one of the subsets ...
- 14.5k