**2**

votes

**1**answer

65 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

86 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

243 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

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

**7**

votes

**1**answer

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

**3**

votes

**1**answer

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

**7**

votes

**1**answer

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

**6**

votes

**0**answers

141 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

126 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

504 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

171 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

154 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

211 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$ ...

**4**

votes

**1**answer

154 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

52 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

337 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

104 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

110 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

83 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

355 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

193 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

396 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

82 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

198 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

383 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

204 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

68 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

420 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

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

**84**

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

**2**

votes

**0**answers

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

**12**

votes

**2**answers

750 views

### Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...

**24**

votes

**3**answers

526 views

### Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...

**5**

votes

**1**answer

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

**2**

votes

**2**answers

517 views

### Asymptotic formula for the number of ways to write a number as the sum of $k$ triangular numbers

How would one derive an asymptotic formula for the number of representations of a number $n$ as the sum of $k$ numbers of the form $\frac{m(m + 1)}{2}$
I think that one could use the circle method, ...

**2**

votes

**2**answers

196 views

### Applications of Szemeredi's Theorem

Szemeredi's Theorem is a famous theorem in Additive Combinatorics, Ergodic Theory and maybe some other parts of Mathemtaitcs:
(Szemeredi's Theorem) Let $\Lambda \in \mathbb{Z}$ be a subset of ...

**2**

votes

**0**answers

50 views

### How is the structure of spectrum in cap-sets with no strong increments unrealistic if density is too large?

I am reading this excellent paper by Bateman and Katz on improved bounds on the cap set problem.
Let A be a set in $\mathbb{F}_3^n$ containing no 3-term arithmetic progression and let $A(x)$ denote ...

**1**

vote

**1**answer

113 views

### Pollard's inequality modulo a composite number

Here is question similar to another one asked today (Proof of Pollard's inequality).
When working in $\mathbb{Z}/n\mathbb{Z}$ for composite $n$ Cauchy-Davenport and Pollard's inequalities may not ...

**2**

votes

**2**answers

169 views

### Proof of Pollard's inequality

Let $A, B \subseteq \mathbb{Z}_p$, $p$ prime, $|B| \leq |A|$.
If $N_t$ denotes the number of elements of $\mathbb{Z}_p$ having at least $t$ representations as $a+b$, $a \in A, b \in B$, Pollard's ...

**2**

votes

**1**answer

110 views

### On a problem about $GF(2)^n$

For $A\subseteq {\mathbb F}_2^n$ let
$$
Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}.
$$
I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then
$$
...

**5**

votes

**3**answers

286 views

### Sets of natural numbers with finite intersections and divergent sums of reciprocals

Does there exist an uncountable collection $\Lambda$ of infinite subsets of the set of natural numbers such that (i) any two distinct subsets in the collection have a finite intersection and (ii) the ...

**2**

votes

**0**answers

102 views

### Applications of Freiman's theorem?

What are some interesting applications of Freiman's theorem or, better-yet, its recent generalizations (eg Green-Ruzsa) that could be included in a graduate course in additive combinatorics?
I'm ...

**8**

votes

**2**answers

590 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

232 views

### Solving a doubly exponential generating function

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...

**3**

votes

**2**answers

210 views

### Number of subsum of a given set of integers

I am asking myself for few days the following but I can't find any references, although I am pretty sure this was already studied, because it seems quite natural:
Given n integers $(e_i)$ chosen ...

**3**

votes

**1**answer

163 views

### Packing bounds for sumsets, or, very discrete balls

Let $D\subset \mathbb{F}_2^n$ with $D=-D$ and $0\in D$. Write $k D$ for the set of all sums of $k$ (not necessarily distinct) elements of $D$. (This is the "ball" in the title.)
Now let $d(g,h)$ be ...

**8**

votes

**3**answers

235 views

### Polynomial expressions of roots of unity with integer norm

Say a nonconstant polynomial $p(z)$ is $k$-magical if it satisfies the following properties:
$p$ is of the form $$p(z) = a_{k-1} z^{k-1} + a_{k-2} z^{k-2} + \cdots + a_1 z + 1$$ where each $a_i \in ...

**11**

votes

**0**answers

331 views

### How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An ...

**1**

vote

**1**answer

120 views

### asymptotic for restricted partitions

Let $m$ and $n$ be two positive integers and denote by $P(n,m)$ the number of partitions of $n$ into $m$ non-negative integers.
Is there an asymptotic formula for $P(n,m)$ ?? Any reference is ...

**2**

votes

**2**answers

181 views

### Functions representable as a sum of two permutations of Z/nZ

Let $\ f:Z/n\rightarrow Z/n\ $ be a function such that $\ \sum_{i\in Z/n}\,f(i)=0.\ $ Is it true that $\ f\ $ can be represented as a sum of two permutations of Z/nZ?