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
Filter by
Sorted by
Tagged with
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 ...
Louis Deaett's user avatar
  • 1,513
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 ...
H A Helfgott's user avatar
  • 19.3k
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 ...
Jakub Konieczny's user avatar
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{...
Pietro Majer's user avatar
  • 56.5k
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 ...
Taras Banakh's user avatar
  • 40.8k
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 ...
Seva's user avatar
  • 22.8k
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 ...
Douglas Zare's user avatar
  • 27.8k
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))\...
Yaakov Baruch's user avatar
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\...
Hailong Dao's user avatar
  • 30.3k
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,\, \...
Alufat's user avatar
  • 805
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 ...
monkeymaths's user avatar
  • 1,169
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}|...
Vesselin Dimitrov's user avatar
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 ...
Ben Barber's user avatar
  • 4,579
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 ...
Wolfgang's user avatar
  • 13.2k
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}...
Dustin G. Mixon's user avatar
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 ...
Joachim Worthington's user avatar
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 ...
Fedor Petrov's user avatar
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 \...
Dylan Airey's user avatar
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 ...
Nick Gill's user avatar
  • 11.2k
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$ ...
Johnny Cage's user avatar
  • 1,543
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 ...
Mike's user avatar
  • 703
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 ...
Jozsef Solymosi's user avatar
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 ...
Mohammad Golshani's user avatar
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Igor Rivin's user avatar
  • 95.5k
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 ...
Stanley Yao Xiao's user avatar
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 \...
Yuichiro Fujiwara's user avatar
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$ ...
Andyqian7's user avatar
  • 165
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 ...
Ivan Meir's user avatar
  • 4,782
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 ...
Sean Eberhard's user avatar
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 ...
Seva's user avatar
  • 22.8k
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(...
Sebastien Palcoux's user avatar
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}^+$ ...
Nick Gill's user avatar
  • 11.2k
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:...
Brandon Hanson's user avatar
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 \...
user avatar
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 ...
Christian Bernert's user avatar
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 ...
Ivan Meir's user avatar
  • 4,782
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}/...
Killua Zoldyck's user avatar
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. ...
Yoozer2021's user avatar
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$ ...
fil's user avatar
  • 51
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 ...
JSE's user avatar
  • 19.1k
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 ...
shurtados's user avatar
  • 1,010
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, ...
Zhi-Wei Sun's user avatar
  • 14.4k
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}^{+...
Taras Banakh's user avatar
  • 40.8k
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 ...
Ryan Alweiss's user avatar
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 ...
Farzad Aryan's user avatar
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: ...
Salvo Tringali's user avatar
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: ...
Konstantinos Gaitanas's user avatar
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. ...
Stanley Yao Xiao's user avatar

1
2 3 4 5