# Tagged Questions

Questions on the subject additive combinatorics, also known as arithmetic combinatorics, such as questions on: additive bases, sum sets, inverse sum set theorems, sets with small doubling, Sidon sets, Szemerédi's theorem and its ramifications, Gowers uniformity norms, etc. Often combined with the ...

38 views

### MDAS solution glitch [on hold]

I always get confused with this kind of math problem, How do we solve this problem? Example: 1 * 5 - 10 + 2 = ? Solution 1 [My solution]: Of couse I use MDAS ...
37 views

### Number of classes $\pmod p$ represented by $b_1s^{n-1} + \dots + b_n$ where $ord_p(s) = n$

Let $n \in \mathbb Z$ with $n \ge 3$ and let $p$ be a prime number such that $n|p-1$. Let $a_1,a_2,\dots,a_{2n-1} \in \mathbb Z/p\mathbb Z$. Suppose that the same class is represented by at most $n-1$ ...
48 views

### When are these sums consecutive integers? [closed]

It is possible to construct $\frac{n(n-1)}{2}$ sums which each contain two distinct summands chosen from a set $n$ numbers. For which $n\geq 3$ do there exist a set of $n$ (distinct) integers such ...
114 views

### Small set such that $\{1 , \ldots , n\} \cdot A = \mathbb{Z} / p \mathbb{Z}$

Let $p$ be a large prime and $n < p$. What is the smallest size of a set $A \subset \mathbb{Z} / p \mathbb{Z}$ such that $A \cdot \{1 , \ldots , n\} = \mathbb{Z} / p \mathbb{Z}$? Here $\cdot$ ...
256 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 ...
20 views

### Is budget-additive function a modular set function?

We know that budget-additive function $$f(S) = \min\{B,\sum_{i \in S}w_i\}$$ where $w_i$ is positive constant and $B \ge 0$ is called additive budget. Is it also a modular set function?
320 views

### On Sylvester's coin problem for geometric progressions

Given $a,b\in\Bbb N$ we know from http://www.emis.ams.org/journals/INTEGERS/papers/i33/i33.pdf that the smallest number that cannot be written as a non-negative linear combination of integers with ...
206 views

1k views

### When does $P(a−b)=0$ for $a≠b$ ensure $P(0)=0$? (Continued.)

As a natural (and expectable) extension of my earlier question: How large must be a set $A\subset F_2^n$ to ensure that if $P$ is a cubic polynomial in $n$ variables over the field $F_2$, ...
336 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 ...
516 views

286 views

Consider the following properties for a subset $A$ of $\mathbb{N}$: (1) $A$ is large: $\sum_{n \in A}$$1\over n$$=\infty,$ (2) $A^\infty=\limsup \frac{|A \cap \{ 1, \dots, n\}|}{n} >0$, (3) $A_\... 1answer 127 views ### 3-dimensional vectors satisfying certain equalities Question: Are there 5 distinct vectors$u,v,w,x,y \in \mathbb{R}^3$, all on the unit sphere (i.e.$||u||=||v||=||w||=||x||=||y||=1$), such that:$||u+v+x||=||u+v+y||=||u+w+x||=||u+w+y||=1$? Also, ... 1answer 447 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: ... 1answer 358 views ### Does$|A+A|$concentrate near its mean? Fix$N$to be a large prime. Let$A \subset \mathbb{Z}/N\mathbb{Z}$be a random subset defined by$\mathbb{P}(a \in A) = p$, where$p = N^{-2/3 + \epsilon}$for some fixed$\epsilon > 0$. My ... 1answer 717 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 ... 0answers 228 views ### The original proof of Szemerédi's Theorem Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ... 1answer 314 views ### Additivity of upper densities with respect to arithmetic progressions of integers Let$\mathsf{d}^\star$be the asymptotic upper density, defined on the power set of positive integers$\mathbf{N}^+$, so that $$\mathsf{d}^\star\colon \mathcal{P}(\mathbf{N}^+) \to\mathbf{R}\colon X\... 1answer 164 views ### Freiman-isomorphic sets Haw can we prove that an arbitrary set A of n positive integers is 2-Freiman isomorphic to a subset of { 1,2,...,4^{n}} and 4^{n} cannot be improved to 2^{n}? 1answer 165 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 ... 1answer 58 views ### l-wise t-intersecting families of shifts of finite sets of integers Let A be a finite set of non-negative integers and write I_k for the set {0,1,\ldots,k-1}. Form all possible l-wise intersections (A+k_1)\cap \ldots \cap (A+k_l), where each k_i runs through ... 1answer 267 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,... 2answers 119 views ### Partition regular systems: do they have solution in (very dense) set of integers? A partition regular system is a linear system of equations of the form A\cdot x=0, which satisfies a Ramsey-type result (namely, that for each r>0 whenever we colour the integers in r classes,... 1answer 100 views ### Intersections of translates of finite sets of integers I am searching for a result in the literature that I am sure must be known, but I just fail to find it. Let us starts with a simple example: Let A, B\subset \mathbb{Z} be a finite sets of integers ... 0answers 84 views ### Consecutive integers divisible by consecutive small numbers Given n, what is the largest set of consecutive integers in [n,2n] can we have so that each integer is divisible by a distinct element from [\log n,2\log n] (no partiular order)? So apriori I am ... 0answers 71 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: ... 0answers 55 views ### \mathsf{GCD}s of random linear form Given a,b\in\Bbb N_{<M} where M\in\Bbb N_{>\exp(18)} is arbitrary with (a,b)=1, the probability that \mathsf{gcd}(ax_1+by_1,ax_2+by_2)=1 where x_1,x_2,y_1,y_2\in\Bbb N_{>\ln M} is ... 1answer 148 views ### Exact statistics in the Frobenius coin problem The Frobenius coin problem guarantees that if (a,b)=1, then$$ax+by$$does not represent exactly$\frac{(a-1)(b-1)}2$numbers all below$g(a,b)=ab-a-b$if$x,y\geq0$holds. Assume$m\in[0,ab-a-b]$... 0answers 216 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 ... 0answers 301 views ### A characterization of quadratics similar to an inverse sieve problem Suppose$\mathscr{A} \subset \mathbb{N}$enjoys for all large enough cutoffs$X$the following properties:$|\mathscr{A} \cap [1,X]| > \sqrt{X}/10$; and the discriminant$\prod_{\alpha \neq \beta}...
A fundamental object in modern additive combinatorics and harmonic analysis is additive energy. Given a subset $A$ of (say) an abelian group $G$ the additive energy of $A$ is defined to be the ...
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 ...