**8**

votes

**0**answers

149 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 ...

**6**

votes

**0**answers

199 views

+150

### 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 ...

**11**

votes

**1**answer

573 views

### Where did the term “additive energy” originate?

A fundamental object in modern additive combinatorics and harmonic analysis is additive energy. Given a subset $A$ of (say) an abelian group $G$ the additive energy of $A$ is defined to be the ...

**-3**

votes

**0**answers

19 views

### Combinatorial problem - 6 classic dices [migrated]

can anyone help me with this task?
We throw with 6 classic(cube) dices. Two are yellow, two are blue and two are green. After every throw we put them into a line. How many different lines exist if we ...

**5**

votes

**1**answer

776 views

### Coin problem with permutations

Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers.
It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c ...

**8**

votes

**1**answer

255 views

### Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le ...

**8**

votes

**0**answers

150 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 ...

**5**

votes

**0**answers

161 views

### Is $AA+A$ always at least as large as $A/A$?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A/A|$?
In the line above, $AA+A:=\{ab+c:a,b,c \in A \}$, while $A/A:=\{a/b:a,b \in A, b\neq 0 \}$ is the ratio set.
...

**6**

votes

**1**answer

220 views

### Subsets of [1..N] with no three-term arithmetic progressions and no large gaps

Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...

**42**

votes

**3**answers

3k views

### Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?

**6**

votes

**2**answers

224 views

### Additive energy of Piatetski-Shapiro sequences

Let $c>1$, and let $A$ denote the set
$$
\Big\{ \lfloor n^c \rfloor, \quad 1 \leq n \leq N \Big\}.
$$
Thus $A$ consists of the first $N$ elements of a so-called Piatetski-Shapiro sequence.
The ...

**1**

vote

**1**answer

147 views

### limit and combinatorics

Given $x \in (0,\frac{1}{2})$ and $y \in (0,\frac{1}{2}]$, what is the value of the following limit:
$\lim_{n\rightarrow \infty}\sum_{k=0}^{n}{n \choose k}|x^{n-k}(1-x)^{k}-y^{n-k}(1-y)^{k}|?$
When ...

**5**

votes

**0**answers

180 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 ...

**2**

votes

**0**answers

108 views

### Additive combinatorics and a Diophantine equation

Let $(n_k)_{1 \leq k \leq N}$ be a sequence of distinct positive integers. For $v \in \mathbb{Z}$ set
$$
A_N(v) = \# \Big\{ (k,\ell) \in \{1, \dots, N\}^2, ~k \neq \ell:\quad n_k - n_\ell = v \Big\}.
...

**20**

votes

**1**answer

654 views

### Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$
In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$
only when we sum the last summand?
For ...

**13**

votes

**1**answer

456 views

### Erdös-Turán via Hardy-Littlewood circle method?

For any set $B\subseteq \mathbb{N}$ one can associate the formal series
$$f_B(z) = \sum_{b\in B}z^b$$
and obtain
$$f_B(z)^k = \sum_{n\geqslant 0} r_{B,k}(n)z^n,$$
where $r_{B,k}(n) = ...

**3**

votes

**2**answers

244 views

### Is the sumset or the sumset of the square set always large?

Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$.
Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity:
$$\max ...

**10**

votes

**2**answers

724 views

### Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression.
I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid
...

**3**

votes

**0**answers

154 views

### On covering by smooth numbers

Denote $P(n)=\mathsf{greatest}\mbox{ }\mathsf{prime}\mbox{ }\mathsf{factor}\mbox{ }\mathsf{of}\mbox{ }n$.
Denote $S(x,y)=\{n<x: P(n)<y\}$.
Denote $S_t(x,y)=\sum_{i=1}^tS(x,y)$ as $t$-fold ...

**18**

votes

**0**answers

467 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 ...

**4**

votes

**0**answers

204 views

### Area defined with $\pm$ closedness

Denote $B_n\subset\Bbb R^n$ to be unit ball at origin.
Denote $S\subset B_n$ to region of type $\mathsf I$ if it satisfies
$$s\in S\iff\forall t\in S, s+t\in S\mbox{ or }s-t\in S$$
I am convinced ...

**6**

votes

**1**answer

243 views

### What pairs of sets have additive energy?

In an abelian group, the additive energy between two sets is $$E(A,B)=|\{(a_1,a_2,b_1,b_2)
\in A\times A\times B\times B:a_1+b_1=a_2+b_2\}|$$ which is ranges from $|A||B|$ to $(|A||B|)^{3/2}$. What I ...

**2**

votes

**1**answer

72 views

### Elaboration of a certain section of a paper by Thanigasalam

In section 11 of this paper by Thanigasalam, it says "... we get $G(10)\le 105$, and this implies that $H(10) \le 107$". However, it is very unclear how this follows. Why is it the case that $G(10)\le ...

**0**

votes

**0**answers

99 views

### Determing signs of Taylor coefficients in entire functions

This is a continuation of Determining when combinatorial sums are zero
Suppose $f(x)$ is an entire function approximated by polynomials with only negative real zeros. Suppose further that ...

**6**

votes

**2**answers

270 views

### Determining when combinatorial sums are zero

To keep things simple with a specific example, we ask:
Prove that $\displaystyle\ a_n:=\frac{1}{n!}\sum_{k=0}^n \binom{n}{k} \frac{1}{k!} (-1)^{n-k}$ is zero if and only if $n=1$. (Or find a ...

**1**

vote

**1**answer

116 views

### On the upper Banach density of the set of positive integers whose base-$b$ representation misses at least one prescribed digit

Let $b$ be a fixed integer $\ge 2$ and $A$ a proper subset of $\{0, \ldots, b-1\}$. Then define $X$ to be the set of all positive integers whose base-$b$ representation consists only of digits from ...

**8**

votes

**1**answer

294 views

### Who was/were the first to note that if $\sum_{x \in X} \frac{1}{x} < \infty$ then the natural density of $X$ is zero?

It is a result from additive-theory folklore that the natural density of a set $X$ of positive integers such that $\sum_{x \in X} \frac{1}{x} < \infty$ is zero. This is reproved, e.g., in T. ...

**7**

votes

**0**answers

150 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 ...

**3**

votes

**0**answers

130 views

### Goldbach's problem in algebraic number fields [duplicate]

Are there any results on the representation of numbers in algebraic number fields as the sum of primes in the ring of integers in that field? There are some results for Waring's problem in other ...

**5**

votes

**3**answers

508 views

### Any rigorous way to claim that sums with repeat summands are few?

Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT ...

**3**

votes

**1**answer

178 views

### When are the powers of 2 sum-free mod n?

I've encountered the following question in my research:
Let $A$ be a subset of
$\mathbb{Z}/n\mathbb{Z}$. Let me call $A$ "sum-free" if there is no solution to
$x+y=z$ for $x,y,z \in A$ with distinct ...

**3**

votes

**1**answer

166 views

### higher dimensional analogue of EGZ theorem

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$.
Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is ...

**4**

votes

**1**answer

243 views

### Ref. request: Additive probability measure on $\mathcal P({\bf N})$ supplies subset of $\mathbf R$ without Baire property

ZFC proves, among the other things, the existence of a (finitely) additive probability measure $\theta: \mathcal P(\mathbf N) \to \mathbf R$ on the power set of $\mathbf N$ such that $\theta(X) = 0$ ...

**5**

votes

**1**answer

163 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 ...

**1**

vote

**0**answers

59 views

### Does there exist $k\ge2$ s.t. $X \subseteq \mathbf N^+$ has positive upper Banach density if the counting function of $X$ is $\gg n/\log^{[k]}(n)$?

Does there exist an integer $k \ge 1$ such that ${\sf bd}^\ast(X) > 0$ whenever $X \subseteq \mathbf N^+$ and $\pi_X(n) \gg \frac{n}{\log^{[k]}(n)}$ as $n \to \infty$? Here, ${\sf bd}^\ast$ is the ...

**3**

votes

**2**answers

361 views

### Who needs a symmetric upper asymptotic density on the integers?

The upper asymptotic density on $\mathbf Z$, viz. the function
$$
{\sf d}^\ast: \mathcal P(\mathbf Z) \to [0,1]: X \mapsto \limsup_{n \to \infty} \frac{|X \cap [1,n]|}{n},
$$
has a ''symmetric ...

**2**

votes

**1**answer

107 views

### Representation numbers of numerical semigroups

I've been playing around with numerical semigroups lately. I'm pretty new to this stuff, so I apologize in advance if my notation is non-standard. Fix positive integers $x_1,\dots,x_r$ with ...

**4**

votes

**1**answer

122 views

### Approximate homomorphisms

Let $f:Z_2^n \to Z_p$ be a one-to-one map, where say $2^n<p<2^{n+1}$. What is the maximal probability that $\Pr[f(x+y)=f(x)+f(y)]$ where $x,y \in Z_2^n$ are uniform and independent? The identity ...

**4**

votes

**0**answers

97 views

### Sparsifiers for 3-term arithmetic progressions

Let $G$ be a finite abelian group of odd order, let $D\subseteq G$, and $\epsilon \in (0,1)$.
For $S\subseteq G$ define
$$
\Lambda(S) = \frac{1}{|S||G|} \sum_{s\in S}\sum_{g\in G} ...

**9**

votes

**2**answers

387 views

### Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?

The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly.
Is it true that for any finite set $A$ of real numbers, and any real ...

**1**

vote

**1**answer

201 views

### Ask the name of a combinatorial theorem

It is a classical theorem. For given integer $n \ge 1$, among ${n\choose{n/2}} = 2^{(1-o(1)n)}$ strings in the cube $\{0, 1\}^n$ with weights $n/2$, i.e., $n/2$ indices are 1, there are at least ...

**18**

votes

**0**answers

420 views

### Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...

**3**

votes

**0**answers

91 views

### Reference for a lemma on the asymptotic upper density of special sets with large gaps and intervals

Update. Based on Anthony Quas' comment below, the proof can be made sensibly shorter and the lemma can be slightly generalized by weakening the old assumption (iii).
In a joint paper that I am ...

**5**

votes

**2**answers

208 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 ...

**13**

votes

**1**answer

391 views

### Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...

**6**

votes

**2**answers

210 views

### What methods do we have to understand the spectrum of matrices with restricted entries?

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $n \times n$ matrix ...

**0**

votes

**1**answer

72 views

### What is the maximal number of solutions of $\sum_{i = 1}^n 1/a_i^x - \sum_{i = 1}^m 1/b_i^x = 0$?

What is the maximal number of solutions of the following equation?
$\sum_{i = 1}^n 1/a_i^x - \sum_{i = 1}^m 1/b_i^x = 0$
where $x$ is the unknown and $n, m$, $a_i$'s, $b_i$'s are constant.
It ...

**6**

votes

**3**answers

430 views

### Conditions for an analogue of Cauchy-Davenport for simple groups

What conditions would be sufficient for a generalization of Cauchy-Davenport for simple groups? I can see two possible difficulties with a generalization for general groups:
The sets could both be ...

**0**

votes

**0**answers

116 views

### Generalized arithmetic progressions contained in Bohr sets

Recall that generalized arithmetic progression of dimension $d$ is by definition a set of the form $P = P_1+\dots+P_d$, where $P_j = \{lp_j\ \mid \ |l|\leq l_j\}\subset \mathbb Z$ is an ordinary ...

**87**

votes

**7**answers

4k views

### Is the set $ AA+A $ always at least as large as $ A+A $?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...