All Questions
Tagged with co.combinatorics additive-combinatorics
42 questions
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
7
votes
1
answer
760
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
- 123
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
18
votes
1
answer
890
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,377
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
3
votes
0
answers
193
views
A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$
Motivated by Question 315568 of mine, I'm interested in the set
$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$
It is easy to see that
$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
- 15.6k
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
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
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
18
votes
4
answers
2k
views
Number of vectors so that no two subset sums are equal
Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \...
- 3,377
5
votes
2
answers
516
views
Anticoncentration of the convolution of two characteristic functions
Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A \...
- 696
2
votes
1
answer
179
views
Only trivial solution to a pair of constrained linear diophantine equations
Given positive integer $n$, we are looking for a set
of $n$ positive integers $a_i$.
The following linear integer program must have only
the trivial integer solution of all ones.
$0 \le x_i \le \frac{...
- 25.4k
1
vote
1
answer
195
views
Covering a finite ring with arithmetic progressions
Let $n\geq 2$ be a positive integer and $k$ be a number between $1$ and $n$. Recently, I came across the following question about $\mathbb Z/n\mathbb Z$ and I wonder if it was studied before. I'd be ...
- 1,625
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
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
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
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
17
votes
2
answers
2k
views
A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem
Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...
- 4,862
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
633
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 ...
- 197
13
votes
1
answer
468
views
Near-linear mappings from $\mathbb F_p$ to $\mathbb R$
$\newcommand{\F}{{\mathbb F}}$
$\newcommand{\R}{{\mathbb R}}$
$\renewcommand{\phi}{\varphi}$
Let $p\ge 5$ be a prime.
If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
- 23k
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 \...
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
9
votes
0
answers
297
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 ...
- 1,169
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
0
answers
304
views
A strong sum-product "for translates" in finite fields
In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...
- 11.2k
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
399
views
Maximum size of $k$-Sidon set over $\mathbb{F}_2^n.$
Fix $k \in \mathbb{N}$, $k \ge 2.$
Does there exist a subset $A \subset \mathbb{F}_2^n$ such that $|A| \ge c 2^{n/k}$ with some absolutely positive constant $c,$ and satisfying
$$ a_1 + a_2 + \...
user148117
7
votes
1
answer
509
views
A permutation problem
Here I ask a question on permutations of $n$ distinct real numbers.
QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...
- 15.6k
5
votes
1
answer
261
views
Divisibility labeling on a boolean lattice and nonzero Euler totient
Let $B_n$ be the subset lattice of $\{1,2, \dots , n \}$, also called the boolean lattice of rank $n$.
A labeling $f: B_n \to \mathbb{N}_{\ge 1}$ is called acceptable if $\forall a,b \in B_n$:
...
4
votes
2
answers
427
views
How big must the sumset $A+A$ be if $A$ satisfies no translation-invariant equations of low height?
Suppose $A$ is a finite subset of an abelian group. If there is no solution to $ma+nb=(m+n)c$ with $0\leq m,n\leq M$, can we bound $|A+A|$ from below? I am interested if one can obtain bounds much ...
- 41
4
votes
1
answer
373
views
Difference set of difference set
I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties.
Property 1 / Step 1
All pairwise differences of the elements should ...
- 73
3
votes
0
answers
144
views
Flat polynomials with factors of big height
Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
- 13.4k
3
votes
0
answers
187
views
Szemerédi’s theorem in really dense sets
This question is inspired by Tao’s answer in this post. I have thought about this occasionally for several months without anything concrete.
Question:
Given $\delta>0$ and $k\ge 3$, let $N= N_k(\...
- 3,499
3
votes
1
answer
318
views
Problem related to Frobenius coin problem
Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ good if,
for any $r,s,u,...
- 13.9k
3
votes
3
answers
748
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 (|\...
- 13k
3
votes
1
answer
260
views
Davenport constant $D(S_5)=10$ or $11$?
I am working on computing the Davenport constant $D(G)$
of symmetric groups, which is the minimal number $d$
such that every sequence of $d$
elements, possibly with repetitions, is one-product, i.e. ...
2
votes
0
answers
143
views
A set in Z/nZ which contains two elements, one of which is a small multiple of the other
While doing my research, I came across yet another problem in $\mathbb Z/n\mathbb Z$ (see my previous question on a related matter here).
Let $n$ be a prime and let $k$ be an integer, $1 \leq k \leq ...
- 1,625
2
votes
1
answer
621
views
On 'Improved Bounds for the Sunflower Lemma' [Alweiss, Lovett, Wu, Zhang]
I have been reading the paper 'Improved Bounds for the Sunflower Lemma' (Ann. of Math., Vol. 194(3), pp. 795-815), and have not managed to understand the following:
I would like a formalization for ...
user469866
1
vote
0
answers
147
views
Counting Hamiltonian cycles in graph and finding a coefficient of polynomial
Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its
adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[...
- 25.4k
1
vote
1
answer
466
views
Some divisibility constraints in Frobenius coin problem
Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...
- 13.9k