All Questions
30 questions
32
votes
2
answers
3k
views
The Erdős–Turán conjecture or the Erdős conjecture?
This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics:
Conjecture: If $A\subset \mathbb{N}$ and $$\...
- 11.4k
17
votes
1
answer
701
views
Combinatorics problem about sum of natural numbers
Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6)
Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each $...
- 422
15
votes
4
answers
575
views
Are all partial consecutive harmonic subsums distinct?
Let $b \gt a \geq 0$ be integers, and as elsewhere let $H_n$ be $\sum^n_{i=1} 1/i$. A partial consecutive harmonic subsum is a number $H(a,b)$ of the form $H_b - H_a$ (with $ H_0=0$). If $c=a$ and $...
- 13k
13
votes
2
answers
931
views
Did Erdős publish his proof of the multiplicative version of the Erdős-Turán conjecture?
I read in an article of Erdős ("Extremal problems in number theory") that he had a proof of the multiplicative version of the Erdős-Turán conjecture. The statement of this theorem is
Let $a_1 < ...
- 85.6k
13
votes
2
answers
880
views
Arithmetic progressions modulo $p$ under the squaring map
I feel that the following problem should be known, but I'm not sure where to look for it.
Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of ...
user631
12
votes
1
answer
307
views
Partition of [3n] into summoids
Let $ [n] $ be the set $ \{1,2,\ldots n\}$.
A summoid is a subset $ A \subset [n] $ of the form $ \{a,b,a+b\} $ (you can choose a better name, if it doesn't exist already).
Now, I developed by ...
11
votes
2
answers
1k
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
...
- 151k
11
votes
2
answers
826
views
Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$
I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...
- 2,851
10
votes
1
answer
554
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 of 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. Šalát's paper: ...
- 10.5k
10
votes
1
answer
554
views
Sidon sets of $\mathbb{Z}/p\mathbb{Z}$
A set $S \subseteq \mathbb{Z}/p\mathbb{Z}$ is called a Sidon set if given $a, b, c, d \in S$ and $a+ b = c+ d$, then $\{a, b\} = \{c,d\}$. I was interested in knowing about the largest possible Sidon ...
- 3,625
8
votes
1
answer
571
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 ...
- 19.2k
7
votes
1
answer
488
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$ ...
- 10.5k
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 \...
- 10.5k
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: ...
- 10.5k
4
votes
2
answers
784
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 welcome....
- 2,384
4
votes
2
answers
676
views
Reference to a variant of Abel's summation formula
Edit. A stronger version of the formula is true (details follow).
Let $(a_n)_{n \ge 1}$ be a sequence of complex numbers, $(\lambda_n)_{n \ge 1}$ a nondecreasing sequence of positive reals such that $...
- 10.5k
4
votes
0
answers
164
views
Two variants of the Littlewood-Offord theorem
I found two different looking things being called the Littlewood-Offord theorem,
If $\vec{a} \in \mathbb{R}^k \setminus 0$ and $t \in \mathbb{R}$ then there are $O(\frac{2^k}{\sqrt{k}})$ points $x \...
- 2,246
3
votes
1
answer
171
views
Does positive relative density imply asymptotic additive basis behaviour?
First definitions: let $A, B \ \subset \mathbb{Z_{>0}}$ and $1\in A, 1\in B$. We define the relative density of $A$ with respect to $B$ to be $$rel(A, B) = \inf_n \frac{|A \cap [1,n]|}{| B \cap [1,...
3
votes
2
answers
621
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 ...
- 10.5k
3
votes
1
answer
528
views
Karolyi's theorem for finite groups and its extensions
Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the ...
- 10.5k
3
votes
1
answer
2k
views
Queries about the Skolem-Mahler-Lech theorem (integer zeros of exponential polynomials)
The Skolem-Mahler-Lech Theorem says that the integer zeros of an exponential polynomial are the union of complete arithmetic progressions and a finite number of exceptional zeros. http://terrytao....
- 1,795
3
votes
0
answers
186
views
Bourgain-Gamburd-like theorems in the non-algebraic case
For $\mu$ a Borel probability measure on the compact group $G=\operatorname{SU}(d)$, Bourgain-Gamburd prove that the spectral radius of the associated operator on $L^2(G)$ is strictly less than one, ...
- 31
3
votes
0
answers
133
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 ...
- 10.5k
2
votes
1
answer
596
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 $A$...
- 10.5k
2
votes
2
answers
393
views
Playing leapfrog with primes
In connection with how primes jump (How do these primes jump?),
I consider the following game.
Let $R$ be a finite set of positive integers. For this question, I content myself with $R$ being the $k$ ...
- 13k
2
votes
0
answers
278
views
On $(k,\ell)$-sumfree sets
Call a set $\mathcal S \subset \mathbb N$ to be $(k,\ell)$-sumfree if there are no non-trivial solutions to the equation
$$x_1+\dots +x_k = y_1+\dots +y_\ell$$
in the set (for distinct $x_i$'s and $...
- 791
2
votes
0
answers
99
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 ...
- 10.5k
2
votes
0
answers
564
views
Sets of coprime numbers
Consider the set $\{0, 3, 7, 15\}$ of four integers. If you add each of these numbers to a fixed power of 2, then the resulting four numbers are pairwise coprime. For example, $\{4, 7, 11, 19\}$ are ...
- 595
1
vote
1
answer
262
views
Distribution of colors in the number of integer partitions of n
Given an integer $n$ the number of partitions of $n$ into two colors can be represented as
$$p_2(n)=\sum_{k=0}^n p(k)p(n-k)$$ where $p(k)$ counts the number of ordinary partitions of $k.$ What is the ...
- 1,306
1
vote
0
answers
98
views
Reference request for a result in additive combinatorics
Let $p$ be a prime number and $[p-1]=\{1, 2, \ldots, p-1\}$.
The following proposition is proved: (but I cannot find out where)
Proposition: The non-empty subset sums of $[p-1]$ are equally ...
- 3,866