All Questions
122 questions
113
votes
7
answers
8k
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 ...
- 1,498
59
votes
2
answers
4k
views
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
I am currently working on a proof that would need to use the following theorem that I cannot prove:
"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
- 643
58
votes
3
answers
6k
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)$?
- 897
44
votes
4
answers
2k
views
Sets of unit fractions with sum $\leq 1$
Consider a set of fractions $\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\right\}$. How many subsets of this set have sum at most 1? I'm interested in the asymptotics of this number.
...
- 5,590
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
- 703
28
votes
3
answers
969
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 $a_1,...
- 281
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
- 109k
26
votes
1
answer
1k
views
probability of zero subset sum
Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not).
Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
- 37.7k
26
votes
0
answers
910
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 ...
- 1,513
24
votes
4
answers
3k
views
What is the shortest route to Roth's theorem?
Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
- 7,013
23
votes
3
answers
3k
views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
- 323
21
votes
1
answer
739
views
Does $A-A=\mathbb Q$ hold for $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$?
Let $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$. Then
$$A-A:=\{a-b:\ a,b\in A\}=\{u^4+v^4-x^4-y^4:\ u,v,x,y\in\mathbb Q\}.$$
Motivated by Question 415482, here I ask the following question.
Question. Is it true ...
- 15.6k
21
votes
1
answer
773
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 ...
- 3,866
19
votes
3
answers
1k
views
The sum of integers being a bijection
What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...
- 52.3k
19
votes
4
answers
865
views
Size of sets with complete double
Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...
- 30.5k
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
17
votes
1
answer
1k
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 ...
- 2,283
16
votes
2
answers
1k
views
The Stable Set Conjecture
A set $\mathcal S$ of positive integers is called stable if for every fixed positive integer $d$, the relation
$$n\in \mathcal S \iff dn\in \mathcal S$$
holds for almost all positive integers $n$. ...
- 791
15
votes
2
answers
750
views
Subsets of $(\mathbb{Z}/p)^{\times n}$
There seems to be some combinatorial fact that every subset $A$ of $G=(\mathbb{Z}/p)^{\times n}$ of cardinality $\frac{p^n-1}{p-1}+1$ containing $\vec{0}$ satisfies $(p-1)A=G$. ($p$ is a prime number....
- 153
15
votes
1
answer
835
views
Goldbach-type theorems from dense models?
I'm not a number theorist, so apologies if this is trivial or obvious.
From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...
- 12.6k
15
votes
1
answer
417
views
What is the smallest cardinality of a self-linked set in a finite cyclic group?
A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$.
For a finite group $G$ denote by $sl(G)$ the smallest ...
- 41.8k
14
votes
1
answer
395
views
Is there a strictly increasing sequence such that it is o(2^n) and any term cannot equal the sum of any unrepeated predecessors?
Does there exist a strictly increasing sequence $\{a_n\}_{n\in N}$ of natural numbers such that the following two requirements hold:
1, For all $n\in N$, there is NO subset $M$ of $\{0,\cdots ,n-1\}$ ...
- 193
14
votes
2
answers
902
views
Sylvester–Gallai theorem for small sets in a finite field
The well-known Sylvester–Gallai Theorem states that a set of $n>2$ points in $R^2$ not all on a line contains two points such that the line passing through these two points does not contain a third ...
- 13k
13
votes
2
answers
2k
views
Positive integers written as $\binom{w}2+\binom{x}4+\binom{y}6+\binom{z}8$ with $w,x,y,z\in\{2,3,\ldots\}$
Let $\mathbb N=\{0,1,2,\ldots\}$. Recall that the triangular numbers are those natural numbers
$$T_x=\frac {x(x+1)}2\quad \text{with}\ x\in\mathbb N.$$
As $T_x=\binom{x+1}2$, Gauss' triangular number ...
- 15.6k
13
votes
1
answer
2k
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 \mathbb{N}...
- 1,081
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
410
views
Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$
Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...
11
votes
1
answer
494
views
Which of these sums appear most often?
Let $N=\{1,2,3,\ldots, n\}$.
We sum all the elements of every nonempty subset of $N$.
Which sum(s) appears most often? (Let's call this sum a champion).
Using a simple pigeonhole argument a champion ...
- 3,866
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
11
votes
0
answers
830
views
Cliques in the Paley graph and a problem of Sarkozy
The following question is motivated by pure curiosity; it is not a part
of any research project and I do not have any applications. The question
comes as an interpolation between two notoriously ...
- 23k
10
votes
4
answers
1k
views
Binomial coefficient in Andrews' partition book
First of all, I think MathOverflow is a very great community to discuss math, either basic or advanced, and I'm glad to participate here. It's my first post, so I'm sorry if i did anything wrong, and ...
- 103
10
votes
2
answers
926
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}$ ...
- 807
10
votes
2
answers
641
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 $...
- 23k
10
votes
2
answers
676
views
Sets A such that A+A contains the largest set [0,1,..,t]
I look for a reference for the following problem.
Given an integer $k$, find a set $A\subset\mathbb{N}$ with $|A|=k$
that maximizes $t$ such that $\left[0,1,..,t\right]\subset A+A$.
- 572
10
votes
3
answers
902
views
Positive integer combination of non-negative integer vectors
A vector of positive integer numbers with $n$ coordinates is given $a=(a_1,\ldots,a_n)$. It holds that $a_1+\cdots+a_n$ is divisible by some positive integer number $k$. I have checked many cases and ...
- 399
9
votes
0
answers
265
views
If $A+A+A$ contains the extremes, does it contain the middle?
Let $b \ge 1$ and $A\subseteq [0,b]$ be a set of integers (all intervals will be of integers).
Write $hA := \underbrace{A + \ldots + A}_{h\text{ summands}} = \{ \sum_{i=1}^h a_i ~|~a_i \in A,\, \...
- 825
9
votes
0
answers
564
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 ...
- 4,589
9
votes
0
answers
153
views
Why have most maximal cliques of Paley graphs odd size?
I ask this question mainly by curiosity.
See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$.
Is there an explanation ...
- 13.4k
8
votes
1
answer
380
views
Question about estimating random symmetric sums modulo p
Let $n > 0$ be a positive integer (large) and $p > 2$ a fixed prime number. What is the probability that $$\sum_{ 1 \leq i < j \leq n} a_ia_j = 0 \mod p$$ where $a_1, a_2, \dots a_n$ are ...
- 1,101
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
8
votes
0
answers
208
views
Erdös-Fuchs Theorem for multivariate linear forms
Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$.
It is not very difficult to show that if $r(n) > 0$ ...
- 1,561
7
votes
2
answers
603
views
Density version of the Erdős-Graham conjecture
In 2003 E. S. Croot [Ann. of Math. 157(2)(2003), 545-556] proved the Erdős-Graham Conjecture which states that if $\{2,3,\ldots\}$ is partitioned into finitely many subsets then one of the subsets ...
- 15.6k
7
votes
2
answers
845
views
Decomposition of a natural number as sum of positive integers
Let $n \in \mathbb{N}$ be a positive natural number and denote by $f(n)$ the number of decompositions of $n$ of the form $n = a+b+c+d$ where $a,b,c,d > 0$ are also positive natural numbers such ...
- 8,998
7
votes
1
answer
569
views
Upper bound for size of subsets of a finite group that contains a sum-full set
Problem
I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:
Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we
define $k(G)$ be ...
- 1,250
7
votes
1
answer
330
views
Large gaps in Singer's difference sets
This question is related to the question I asked earlier.
For a natural number $n$, a set $D$ of integer numbers is called a $n$-cyclic difference set if each integer number $x\notin n\mathbb Z$ can ...
- 41.8k
7
votes
0
answers
176
views
Sumsets that contains many squares, Improvement on the bound
I'm being troubled by this problem on AoPS:
https://artofproblemsolving.com/community/c6h1998237p13955033
I searched for any literature related to it such as
Nguyen, Hoi H., and Van H. Vu., Squares ...
- 63
7
votes
0
answers
264
views
Is every integer $n>1$ the sum of two squares and two central binomial coefficients?
Those integers $\binom{2n}n\ (n=0,1,2,\ldots)$ are called central binomial coefficients. By Stirling's formula,
$$\binom{2n}n\sim \frac{4^n}{\sqrt{n\pi}}\ \ \ \ (n\to+\infty).$$
Of course, the ...
- 15.6k
6
votes
4
answers
627
views
Request for an exact formula related to a partition in number theory
The Frobenius equation is the Diophantine equation $$
a_1 x_1+\dots+a_n x_n=b,$$
where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$
must consist of non-...
- 10.5k
6
votes
2
answers
1k
views
Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density
It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous ...
- 26.9k
6
votes
5
answers
961
views
What makes a set random?
There are many results in number theory, where the existence
of some $B \subseteq \mathbb{N}$ with certain properties is proved by
a probabilistic argument employing "random sets". One such ...
- 579