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.

Filter by
Sorted by
Tagged with
0
votes
0answers
123 views

For any $n-1$ elements of $\mathbb Z/n\mathbb Z$, we can make $0$ using $\{-,+,\times\}$ without parentheses

MSE: Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n? (no brackets allowed) Is there any hope in proving the following? (Cross-posted here after a ...
3
votes
1answer
169 views

Difference set of difference set

I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties. Property 1 / Step 1 All pairwise differences of the elements should ...
5
votes
0answers
130 views

Does any subset of a finitely generated group with positive upper density contain three points in arithmetic progression?

Let $G$ be a countable finitely generated group, with word metric $d_S$ induced by some generating set $S$. Let $B_r$ be the ball of radius $r$ around the identity under $d_S$. We say that $A \subset ...
7
votes
0answers
221 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}...
0
votes
0answers
33 views

Reference request: Efficient representations of lattice elements as sums of generators

Let $\Lambda$ be a lattice in $V =\mathbb{R}^d$, and let $B \subset V$ be a symmetric, open and bounded set. Put $N = |\Lambda \cap B|$, and suppose that there exist vectors $v_1,\dots,v_s \in \Lambda ...
1
vote
1answer
47 views

Expectation of the sum of the squares of the cardinal of an inverse function

I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as: $$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$ where $\oplus$ is the bitwise XOR. ...
0
votes
0answers
243 views

Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?

Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$. I'm curious whether there is a permutation $\tau\in S_n$ such that $$\tau(1)^{\tau(2)}+\...
14
votes
3answers
272 views

Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set — easy? NP-complete?

Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $n$, a divisor $k$ of $n$, and a subset $S \subset \mathbb{Z}_n$ of size k. The ...
3
votes
0answers
170 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. ...
4
votes
0answers
87 views

Strengthening of Freiman's theorem

Is the following strengthening of Freiman's theorem true? Let $G$ be an abelian group. We say that a set $X\subset G$ is $d$-structured if $X$ is a union of $d$ or less $d$--dimensional (generalized) ...
1
vote
0answers
45 views

Complexity of checking if a set is an additive basis

A set of nonnegative integers $A$ is said to be an additive basis of order $k$ if every nonnegative integer is equal to the sum of $k$ elements of $A$. For example, Lagrange's theorem says that the ...
0
votes
0answers
74 views

Lower Bound on Structured Fourier Coefficients

Consider the unnormalized Fourier coefficients of subsets $D_g$ of $\mathbb Z/n \mathbb Z$, denoted by $$ \hat1_{D_g}(m)=\sum_{d \in {D_g}} e\left (\frac{m d }{n}\right ), $$ where $e(x) = e^{2 i \pi ...
48
votes
3answers
2k views

Is each squared finite group trivial?

A semigroup $S$ is defined to be squared if there exists a subset $A\subseteq S$ such that the function $A\times A\to S$, $(x,y)\mapsto xy$, is bijective. Problem: Is each squared finite group ...
7
votes
1answer
297 views

Bounding size of partial difference sets given size of partial sumsets

In this paper by Katz and Tao, the following bounds were established. Let $A,B$ be finite subsets of an abelian group, with $|A|,|B|\le N$. We fix some $G \subset A\times B$. We define $C = \{a+b:(a,b)...
1
vote
0answers
48 views

Converse to Hausdorff-Young (or Riesz-Thorin) for finite cyclic groups?

Let $v$ be a vector $v \in \mathbb{R}^p$, with non-negative entries and $p$ prime. The Hausdorff-Young inequality gives bounds of the form: $$\|\mathcal{F}v\|_a \le C_{a,b} \|v\|_b$$ where the ...
0
votes
0answers
75 views

Norms of ideals in number fields as additive bases

An (asymptotic) additive basis of order $k$ is a subset $S \subset \mathbb{N}$ with the property that every (sufficiently large) positive integer $m$ can be written as the sum of at most $k$ (not ...
6
votes
0answers
115 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
1answer
168 views

Arithmetic progressions in inverse image of totient function

I noticed on the OEIS that there are various sequences (e.g. A050515-A050520) that describe arithmetic progressions whose totients are all equal. For example, we have $$\varphi(\{1,2\}) = 1$$ $$\...
4
votes
1answer
218 views

A combinatorial problem on abelian groups

In a 1952 paper M. Hall proved that if $G=\{a_1,\ldots,a_n\}$ is an additive abelian group of order $n$ and $b_1,\ldots,b_n$ are elements of $G$ with $b_1+\ldots+b_n=0$ then we have $$\{a_{\sigma(i)}+...
18
votes
1answer
507 views

Characterizing the elements of $(A-A)/(A-A)$, where $A$ is a Cantor-like subset of the integers

Short version of my question: I'm interested in the following fact. If $m,n$ are odd integers, then $m/n$ can be written as the ratio of two numbers of the form $\sum_{j=0}^\ell \epsilon_j 4^j$, ...
8
votes
1answer
123 views

Maximum density of a set without a fixed pattern

Consider a finite set $S$ of nonnegative integers. What is the maximum natural density of an infinite subset of $\mathbb{Z}$ which does not contain any translation of $S$? Of course, this will depend ...
1
vote
0answers
99 views

Counting solutions of a equation involving prime powers

Let $p\geq 3$ be a prime number. Let $n\in\mathbb{Z}_{\geq 1}$, $q\in\mathbb{Q}$, $m\in\mathbb{Z}_{\geq 2}$. Set $$T_n(q,m)=\#\left\{(l_1,\cdots,l_{p^n})\in\mathbb{Z}_{\geq n+m}^{p^n}\middle\vert\sum_{...
10
votes
2answers
837 views

Converse to Erdős' conjecture on arithmetic progressions

I apologise in advance if this has been asked here before. I did a search and did not find anything obvious. Erdős' conjecture states that if $A\subseteq {\bf N}$ is such that $\sum_{n\in A} n^{-1}$ ...
6
votes
1answer
144 views

Analogue to Szemerédi's theorem for non-monotone sequences

Szemerédi's theorem states that a strictly increasing sequence of positive integers $a_0, a_1, \ldots$ whose range has positive density contains arbitrarily long arithmetic progressions (as ...
5
votes
1answer
237 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 ...
1
vote
1answer
84 views

$\ell^1$-bound on graph laplacian with weight

Consider the $\mathbb Z^2$ lattice, we then define for $u=(u_{ij})_{i,j \in \mathbb Z}$ the discrete Laplacian $$(\Delta u)_{i,j}=u_{i+1,j}+u_{i-1,j}+ u_{i,j+1}+u_{i,j-1}$$ and the weight which pushes ...
2
votes
1answer
113 views

What is the importance of “small doubling” in the theory of approximate groups?

One question I have is "why are approximate groups important?". If the small doubling constant is $1$ then it's definitely a group. If I read Green's note correctly. (1, 2) To be more ...
3
votes
0answers
133 views

Ellenberg and Gijswijt's result on arithmetic progressions in subsets of $\mathbb{F}_q^n$ and a generalisation to sets of linear equations

Ellenberg and Gijswijt showed that the largest subset of $\mathbb{F}_q^n$ with no three terms in arithmetic progression has size $c^n$ where $c<q$. Ellenberg and Gijswijt actually proved a ...
7
votes
1answer
170 views

Sets of residues with only a single intersection under translation

A combinatorial game I am studying has given rise to the following question. Consider the group $\Bbb Z/n\Bbb Z$. What is the largest $m$ such that there exist $k$ sets of $m$ residues such that the ...
0
votes
1answer
165 views

Distributions associated with random sets and sums of random sets

Let's say you have an infinite random set $S$ of non-negative integers, and $T=S+S=\{x+y$ with $x,y\in S\}$. Let $N_S(z)$ be the number of elements of $S$ less than or equal to $z$; it is a random ...
6
votes
1answer
851 views

Is there any relationship between Szemerédi's theorem and Sunflower conjecture?

I have observed some similar things between a reformulation of the Sunflower conjecture (see also conjecture 1.3 in Improved bounds for the sunflower lemma) and Szemerédi's theorem such that for ...
2
votes
0answers
78 views

Origins of the ``baby Freiman'' theorem

It is a basic folklore fact from the area of additive combinatorics that a subset $A$ of an abelian group satisfies $|2A|<\frac32\,|A|$ if and only if $A$ is contained in a coset of a (finite) ...
3
votes
1answer
249 views

Prime gap distribution in residue classes and Goldbach-type conjectures

Update on 7/20/2020: It appears that conjecture A is not correct, you need more conditions for it to be true. See here (an answer to a previous MO question). The general problem that I try to solve is ...
11
votes
2answers
711 views

A problem in additive combinatorics

$\color{red}{\mathrm{Problem:}}$ $n\geq3$ is a given positive integer, and $a_1 ,a_2, a_3, \ldots ,a_n$ are all given integers that aren't multiples of $n$ and $a_1 + \cdots + a_n$ is also not a ...
1
vote
1answer
327 views

Congruential equidistribution, prime numbers, and Goldbach conjecture

Let $S$ be an infinite set of positive integers, $N_S(z)$ be the number of elements of $S$ less than or equal to $z$, and let $$D_S(z, n, p)= \sum_{k\in S,k\leq z}\chi(k\equiv p\bmod{n}).$$ Here $\chi$...
1
vote
1answer
331 views

Curious inversion formula in additive combinatorics

Let $S$ be an infinite set of positive integers, and $T=S+S=\{x+y, \mbox{ with } x,y\in S\}$.We definte the following functions: $N_S(z)$ is asymptotic continuous version of the function counting the ...
0
votes
1answer
552 views

Paradox in additive combinatorics

Let $S$ be an infinite set of positive integers. Let us define the following quantities: $N_S(z)$ is the number of elements of $S$, less or equal to $z$ $r_S(z)$ if the number of positive integer ...
0
votes
0answers
112 views

General asymptotic result in additive combinatorics (sums of sets)

Let $S_1,\cdots,S_k$ be $k$ infinite sets of positive integers. Let $N_i(z)$ be the numbers of elements in $S_i$ that are less or equal to $z$. Let us further assume that $$N_i(S) \sim \frac{a_i z^{...
7
votes
0answers
106 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 ...
5
votes
3answers
1k views

Goldbach conjecture and other problems in additive combinatorics

The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance: $S = T$ is the set ...
5
votes
1answer
280 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 ...
5
votes
0answers
96 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 ...
3
votes
0answers
58 views

Almost quadratic difference sets

Does there exist a characterization of sets $S$ such that $|S-S|$ is "almost quadratic" in $|S|$? For instance, what are some examples of sets such that $|S-S|$ is on the order of $\frac{{|S|}^2}{\log ...
2
votes
0answers
80 views

On norms of Boolean functions

Let $f: \mathbb{F}_2^n \rightarrow \{-1,1\}$ be a Boolean function, represented by a $N=2^n$ dimensional vector, $f \in \{-1,+1\}^N$. Define the Fourier transform of $f$ to be $\hat{f}$, where $$\hat{...
6
votes
1answer
223 views

Maximum size of $k$-Sidon set over $\mathbb{F}_2^n.$

Fix $k \in \mathbb{N}$, $k \ge 2.$ Does there exist a subset $A \subset \mathbb{F}_2^n$ such that $|A| \ge c 2^{n/k}$ with some absolutely positive constant $c,$ and satisfying $$ a_1 + a_2 + \...
2
votes
0answers
76 views

Sumset of $k$-smooth numbers

Take the set $T(k,n)=M_1(k,n)$ of all $k$ smooth numbers less than $n$. What is the cardinality of $$\{1,\dots,n\}\cap M_2(k,n)$$ where every integer in $M_2(k,n)$ is the sum of two integers in $M_1(...
5
votes
1answer
110 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\...
1
vote
0answers
99 views

Bell polynomial with variables 1 and 0

Let $B_{n,k}(x_1,\cdots,x_{n-k+1})$ be the Bell polynomial. If $x_1=\cdots=x_{n-k+1}=1$, we know that $B_{n,k}(x_1,\cdots,x_{n-k+1})=S(n,k)$, where $S(n,k)$ is the Stirling number of second kind. ...
3
votes
1answer
192 views

Unique representation and sumsets

Let $A$ be a finite, nonempty subset of an abelian group, and let $2A:=\{a+b\colon a,b\in A\}$ and $A-A:=\{a-b\colon a,b\in A\}$ denote the sumset and the difference set of $A$, respectively. If ...
-2
votes
1answer
189 views

What are the consequence of Snevily's conjecture to analytic number theory if really there is a connection between them? [closed]

Snevily's conjecture it is an open conjecture in Group theory for non cyclic Group and it were proved for abelian groups of prime order using a fairly standard application of the Alon-Tarsi ...

1
2 3 4 5
11