All Questions
37
questions
2
votes
2
answers
60
views
Regarding scaling in sumsets
Let $A$ be a finite subset of $\mathbb{N}$. We denote the set $\{a_1 +a_2: a_1, a_2\in A\}$ as $2A$. We call the quantity $\sigma[A]:= |2A|/|A|$ as the doubling constant of $A$, and this constant can ...
- 971
2
votes
0
answers
111
views
On $s$-additive sequences
For a non-negative integer $s$, a strictly increasing sequence of positive integers $\{a_n\}$ is called $s$-additive if for $n>2s$, $a_n$ is the least integer exceeding $a_{n-1}$ which has ...
- 9,592
1
vote
1
answer
66
views
Sum-free sequence but multiset
The question is:
Show that if $S$ is a set of natural numbers such that no number in S can be expressed as a sum of other (not necessarily distinct) numbers in S, then $\sum_{ s \in S} \frac{1}{s} \...
- 506
0
votes
0
answers
38
views
Schnirelmann density and bases of finite order
Let $\mathcal{A}$ be an additive set. We know that if the Schnirelmann density $\sigma_{\mathcal{A}}$ is positive then it is a basis of finite order. But it it not a necessary condition. My question ...
user1232857
1
vote
1
answer
88
views
If $A \subseteq \mathbb{Z}/p\mathbb{Z}$, and $|A| > \frac{p}{3}$, then are there any nontrivial lower bounds for $|AA|$?
If $A \subseteq \mathbb{Z}/p\mathbb{Z}$, and $|A| > \frac{p}{3}$, then are there any nontrivial lower bounds for $|AA|$?
Where $AA=\{a_{1} \cdot a_2:a_1,a_2 \in A\}$, and $p$ is prime.
Writing out ...
- 196
1
vote
0
answers
23
views
When is the Frobenius number of a numerical semigroup larger than the maximum of the minimal generating set
Let $S$ be a numerical semigroup (https://en.m.wikipedia.org/wiki/Numerical_semigroup). Let $A$ be the minimal generating set for $S$. As standard, let $e(S)$, $m(S)$ and $F(S)$ stand respectively ...
- 65
0
votes
1
answer
54
views
On writing every integer from $(a-1)(b-1)$ onwards as a sum of two non-zero integers from the semigroup generated by $a,b$
Let $\mathbb N$ be the semigroup (even a monoid) of non-negative integers. Let $a<b$ be relatively prime integers such that $2< a$. Let $S :=\mathbb N a +\mathbb N b$ be the semigroup generated ...
- 65
2
votes
1
answer
339
views
Behrend's construction on large 3-AP-free set
Theorem (Behrend's construction)
There exists a constant $C>0$ such that for every positive integer
$N$, there exists a $3$-AP-free $A\subseteq[N]$ with $|A|\geq
Ne^{-C\sqrt{\log N}}$.
Proof. Let $...
- 17k
1
vote
0
answers
115
views
About a proof or disproof of a statement concerning additive bases of natural numbers.
Here $\mathbb{N}=\{1,2,3,\dots\}$.
We say that a set $A\subset\mathbb{N}$ is an additive base of natural numbers if there is
a positive integer $h$ such that every natural number can be written as
$...
5
votes
1
answer
111
views
Is there an examble of a non additive base of natural numbers with ratio of two consecutive terms goes to 1?
Here $\mathbb{N}=\{1,2,3,\dots\}$.
We say that a set $A\subset\mathbb{N}$ is an additive base of natural numbers if there is
a positive integer $h\in \mathbb{N}$ such that every natural number can be ...
2
votes
1
answer
124
views
Roth's Theorem Finitary and Infinitary forms are equal
Theorem1
Let A be a subset of positive integers with positive upper density then A contains a 3 term arithmetic progression.
Theorem2
For any $\delta>0$ there exists $N_{0}$ such that for every $N\...
- 23
1
vote
1
answer
72
views
Upper bound on $\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}$ where $s(J)=\sum_{j\in J}j$
Define $s(J)=\sum_{j\in J}j$ and $[n]=\{1,...,n\}$. I'm trying to get some reasonable upper bound on $$\sum_{J\subset [n], |J|=i}\frac{1}{2^{s(J)}}.$$
Actually, I want an upper bound on $$\sum_{i=k}^{...
- 1,075
3
votes
1
answer
132
views
Understanding Arithmetic Progression in $[N]$ vs. $\mathbb{Z}_N$
For a set $A$ with some underlying addition operator, $r_k(A)$ is the size of the maximum subset of $A$ that does not contain a $k$-term arithmetic progression.
Exercise 10.0.1 in Tao-Vu's Additive ...
- 158
9
votes
1
answer
154
views
Properties of subsets for which $\sum 1/k$ diverges
The well-known Erdos-Turan conjecture is the following.
Let $V \subset \mathbb{N}$ be such that $\sum_V k^{-1}$ diverges. Then $V$ contains arithmetic progressions of every possible length.
A recent ...
3
votes
1
answer
176
views
Determine the structure of all finite sets $A$ of integers such that $|A| = k$ and $|2A| = 2k + 1$.
An exercise in Nathanson's text: Additive Number Theory, Inverse problems and the geometry of sumsets is the following (Excercise 16, P.No.37):
Determine the structure of all finite sets $A$ of ...
- 622
2
votes
1
answer
111
views
Maximal size of bounded “sparse” sets of natural numbers
Let’s call $A \subset \mathbb{N}$ sparse iff for all quadruples of distinct numbers $(a, b, c, d)$ from $A$ it is true, that $a + b \neq c + d$. What is the maximal possible size of a sparse set $A$, ...
- 15.7k
2
votes
1
answer
96
views
Construct an set $A\in\mathbb{N}$ such that $\delta(A)$ exists, but $\delta(A\cap(A+1))$ doesn't exist, where $A+1=\{a+1:a\in A\}$.
Definition: For $A\subset\mathbb{N},$ define the natural density of A to be: $\delta(A)=\lim_{N\rightarrow\infty}\frac{|A\cap\{1,\dots,N\}|}{N}$. We say $\delta(A)$ doesn't exist if the limit $\lim_{N\...
- 1,336
1
vote
0
answers
36
views
On the cardinality of the set $ A(m) := \{ (a, b) \in \mathbb{N}^2 : \; N \leq a \leq 2 N, \; a^2 - b^2 = m \}, $
Question: Consider the set
$$ A(m) := \{ (a, b) \in \mathbb{N}^2 : \; N \leq a \leq 2 N, \; a^2 - b^2 = m \}, $$
where $ \mathbb{Z} \ni m < 0$ and $N \in \mathbb{N} \setminus \{ 0 \}$. Then
...
- 374
8
votes
2
answers
434
views
How to show that $\gcd(a_1,a_2,\cdots,a_k) = 1$ implies that there exist a non-negative solution to $\sum_{i=1}^{n}a_ix_i = n$ for large $n.$
I was reading about the Coin-problem and I am unable to fully understand the following argument:
On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a ...
- 9,258
6
votes
0
answers
131
views
Odd of the form $a^2+b^2+c^2+ab+ac+bc$.
The computation below shows that (for $a,b,c \in \mathbb{N}$) the form $$a^2+b^2+c^2+ab+ac+bc$$ covers every odd integer less than $10^5$ except those in $$I= \{ 5, 15, 23, 29, 41, 53, 59, 65, ...
- 5,847
3
votes
0
answers
65
views
Product set in a finite field
For a finite nonempty subset $A$ of a ring $X=(X,+,\cdot)$, let us denote the set $\{a \cdot b \colon a, b \in X\}$.
If $X=\mathbb{Z}$, it is not difficult to show that
$$|AA| \leq \frac{|A|^{2}+|...
- 577
1
vote
0
answers
45
views
Asymptotic formula for the integral sequence s(n)
Prove that there exists a sequence $A_{0}, A_{1}$, . . . of rational polynomials $A_{i}(x)\in \mathrm{Q}[x]$ with $A_{i}$ of degree $i$ such that
$$
s(n)=\frac{n^{n-1}}{(1-\log 2)^{n-1/2}e^{n}}(\sum_{...
- 11
3
votes
0
answers
65
views
Maximal number of subsets of $n$ real numbers that have the same sum, when $2^{n-2}$ of subsets have "unique" sums
I've recently found a problem that I still can't solve: Dependency of the properties of numbers' subsets concerning subsets' sums of $n$ real numbers.
A problem linked with it, that may be ...
- 41
19
votes
2
answers
645
views
Sumset that covers $\mathbb{Z}/p\mathbb{Z}$.
Let $p$ be a prime. Let $S$ be a set of residues modulo $p$. Define
$$S^2 = \{a \cdot b \mid a \in S, b \in S\}.$$
Question:
How small can we make $|S|$ such that $\{0, 1, \cdots, p-2, p-1\} \in ...
- 8,165
5
votes
2
answers
358
views
Is there any formula for this sum of power of positive integers? [duplicate]
I wonder if there is any formula for this sum.
$$k^\gamma+(k-1)^\gamma+\cdots+1^\gamma,$$
where $k$ is positive integer and $\gamma\in(0,1)$. And how about $\gamma<0$? Or is there any known ...
- 2,075
1
vote
0
answers
60
views
Partitioning a progression
Let $P $ be a $Z_N $ progression of length $R $.Prove that we can partition $P $ into at most $4 \sqrt R $ genuine arithmetic progressions. (Genuine arithmetic progression means arithmetic ...
- 3,493
4
votes
1
answer
326
views
Application of Cauchy-Davenport
Let $ p $ be a prime number and $ A \subset \mathbb{Z}/p\mathbb{Z} $. Suppose $ 0 \notin A $ and for $ a \in A $ define $ d(a)= \min\{k|-a \in \underbrace{A+A+ \dots +A}_\text{k times} \} $. I want ...
- 1,085
1
vote
1
answer
164
views
Changing powers to sums in a simple system of equations
Let's say we have the system of $l$ equations below:
$$
\left\{
\begin{array}{c}
a_{11}^{a_{12}}=a_{13} \\
a_{21}^{a_{22}}=a_{23} \\
\ldots \\
a_{l1}^{a_{l2}}=a_{l3} \\
\end{array}
\right.
$$
...
- 451
8
votes
1
answer
164
views
An analogue of direct sum decomposition of a cofinite subset of integers
Let $S \subseteq \mathbb Z$ be such that $\mathbb Z \setminus S$ is finite , then is it true that there exists infinite $ S_1,S_2 \subseteq \mathbb Z$ such that $S_1+S_2=S$ and for every $s \in S $ , ...
user228169
1
vote
1
answer
51
views
Subset of $\mathbb{Z}_n$ and zero sum
Let $a_1, a_2, \ldots, a_n$ be elements of $\mathbb{Z}_n$. Prove that there exist $r$ and $s$ such that $\sum_{i=r}^s a_i \equiv 0 \pmod n$ (with $1 \leq r \leq s \leq n$).
Do you have any hint? I ...
- 145