BZPEER

preprint2022arXiv

The structure of higher sumsets

Merging together a result of Nathanson from the early 70s and a recent result of Granville and Walker, we show that for any finite set $A$ of integers with $\min(A)=0$ and $\gcd(A)=1$ there exist two sets, the "head" and the "tail", such that if $m\ge\max(A)-|A|+2$ , then the $m$ -fold sumset $mA$ consists of the union of these sets and a long block of consecutive integers separating them. We give sharp estimates for the length of the block, and investigate the corresponding stability problem classifying those sets $A$ for which the bound $\max(A)-|A|+2$ cannot be substantially improved.

preprint2022arXiv

Zero-sum-free sequences with few subsequence sums

We show that a zero-sum-free sequence of length $n$ over an abelian group spans at least $2n$ distinct subsequence sums, unless it possesses a rigid, easily-described structure.

preprint2016arXiv

Minimizing the sum of projections of a finite set

Consider the projections of a finite set $A\subset R^n$ onto the coordinate hyperplanes. How small can the sum of the sizes of these projections be, given the size of $A$ ? In a different form, this problem has been studied earlier in the context of edge-isoperimetric inequalities on graphs, and it is can be derived from the known results that there is a linear order on the set of $n$ -tuples with non-negative integer coordinates, such that the sum in question is minimised for the initial segments with respect to this order. We present a new, self-contained and constructive proof, enabling us to obtain a stability result and establish algebraic properties of the smallest possible projection sum. We also solve the problem of minimising the sum of the sizes of the one-dimensional projections.

preprint2016arXiv

Stability result for sets with $3A\ne{\mathbb Z}_5^n$

As an easy corollary of Kneser's Theorem, if $A$ is a subset of the elementary abelian group ${\mathbb Z}_5^n$ of density $5^{-n}|A|>0.4$ , then $3A={\mathbb Z}_5^n$ . We establish the complementary stability result: if $5^{-n}|A|>0.3$ and $3A\ne{\mathbb Z}_5^n$ , then $A$ is contained in a union of two cosets of an index- $5$ subgroup of ${\mathbb Z}_5^n$ . Here the density bound $0.3$ is sharp. Our argument combines combinatorial reasoning with a somewhat non-standard application of the character sum technique.

preprint2016arXiv

Symmetric Kneser's Theorem with Trios and $3$ -Transform

We give a new equivalent restatement and a new proof in terms of trios to the classical Kneser's theorem. In the finite case, our restatement takes the following, particularly symmetric shape: if $A$ , $B$ , and $C$ are subsets of a finite abelian group $G$ such that $A+B+C\ne G$ , then, denoting by $H$ the period of the sumset $A+B+C$ , we have $|A|+|B|+|C| \le |G|+|H|.$ The proof is based on an extension of the familiar Dyson transform onto set systems containing three (or more) sets.

preprint2015arXiv

Integer sets with identical representation functions

We present a versatile construction allowing one to obtain pairs of integer sets with infinite symmetric difference, infinite intersection, and identical representation functions.

preprint2015arXiv

Quadratic residues and difference sets

It has been conjectured by Sarkozy that with finitely many exceptions, the set of quadratic residues modulo a prime $p$ cannot be represented as a sumset $\{a+b\colon a\in A, b\in B\}$ with non-singleton sets $A,B\subset F_p$ . The case $A=B$ of this conjecture has been recently established by Shkredov. The analogous problem for differences remains open: is it true that for all sufficiently large primes $p$ , the set of quadratic residues modulo $p$ is not of the form $\{a'-a"\colon a',a"\in A,\,a'\ne a"\}$ with $A\subset F_p$ ? We attack here a presumably more tractable variant of this problem, which is to show that there is no $A\subset F_p$ such that every quadratic residue has a \emph{unique}representation as $a'-a"$ with $a',a"\in A$ , and no non-residue is represented in this form. We give a number of necessary conditions for the existence of such $A$ , involving for the most part the behavior of primes dividing $p-1$ . These conditions enable us to rule out all primes $p$ in the range $13<p<10^{18}$ (the primes $p=5$ and $p=13$ being conjecturally the only exceptions).

preprint2014arXiv

Discrete norms of a matrix and the converse to the Expander Mixing Lemma

We define the discrete norm of a complex $m\times n$ matrix $A$ by $\|A\|_Δ:= \max_{0\neξ\in\{0,1\}^n} \frac{\|Aξ\|}{\|ξ\|},$ and show that $\frac c{\sqrt{\log h(A)+1}}\,\|A\| \le \|A\|_Δ\le \|A\|,$ where $c>0$ is an explicitly indicated absolute constant, $h(A)=\sqrt{\|A\|_1\|A\|_\infty}/\|A\|$ , and $\|A\|_1,\|A\|_\infty$ , and $\|A\|=\|A\|_2$ are the induced operator norms of $A$ . Similarly, for the \emph{discrete Rayleigh norm} $\|A\|_P := \max_{\substack{0\neξ\in\{0,1\}^m \\ 0\neη\in\{0,1\}^n}} \frac{|ξ^tAη|}{\|ξ\|\|η\|}$ we prove the estimate $\frac c{\log h(A)+1}\,\|A\| \le \|A\|_P \le \|A\|.$ These estimates are shown to be essentially best possible. As a consequence, we obtain another proof of the (slightly sharpened and generalized version of the) converse to the expander mixing lemma by Bollobas-Nikiforov and Bilu-Linial.

preprint2013arXiv

Approximate convexity and an edge-isoperimetric estimate

We study extremal properties of the function $F(x) := \min\{k\|x\|^{1-1/k}\colon k\ge 1\},\ x\in[0,1],$ where $\|x\|=\min\{x,1-x\}$ . In particular, we show that $F$ is the pointwise largest function of the class of all real-valued functions $f$ defined on the interval $[0,1]$ , and satisfying the relaxed convexity condition $f(tx_1+(1-t)x_2) \le tf(x_1)+(1-t)f(x_2)+|x_2-x_1|, \ x_1,x_2,t\in[0,1]$ and the boundary condition $\max\{f(0),f(1)\}\le 0$ . As an application, we prove that if $A$ and $S$ are subsets of a finite abelian group $G$ , such that $S$ is generating and all of its elements have order at most $m$ , then the number of edges from $A$ to its complement $G\setminus A$ in the directed Cayley graph induced by $S$ on $G$ is $\partial_S(A) \ge \frac{1}{m} |G| F(|A|/|G|).$

preprint2013arXiv

Flat-containing and shift-blocking sets in $F_2^r$

For non-negative integers $r\ge d$ , how small can a subset $C\subset F_2^r$ be, given that for any $v\in F_2^r$ there is a $d$ -flat passing through $v$ and contained in $C\cup\{v\}$ ? Equivalently, how large can a subset $B\subset F_2^r$ be, given that for any $v\in F_2^r$ there is a linear $d$ -subspace not blocked non-trivially by the translate $B+v$ ? A number of lower and upper bounds are obtained.

preprint2012arXiv

Edge-isoperimetric problem for Cayley graphs and generalized Takagi function

Let $G$ be a finite abelian abelian group of exponent $m\ge 2$ . For subsets $A,S\subset G$ , denote by $\partial_S(A)$ the number of edges from $A$ to its complement $G\setminus A$ in the directed Cayley graph, induced by $S$ on $G$ . We show that if $S$ generates $G$ , and $A$ is non-empty, then $\partial_S(A) \ge \frac{e}m\,|A|\ln\frac{|G|}{|A|}.$ Here the coefficient $e=2.718...$ is best possible and cannot be replaced with a number larger than $e$ . For homocyclic groups $G$ of exponent $m$ , we find an explicit closed-form expression for $\partial_S(A)$ in the case where $S$ is a "standard" generating subset of $G$ , and $A$ is an initial segment of $G$ with respect to the lexicographic order, induced by $S$ on $G$ . Namely, we show that in this situation $\partial_S(A) = |G|\,ω_m(|A|/|G|),$ where $ω_2$ is the Takagi function, and $ω_m$ for $m\ge 3$ is an appropriate generalization thereof. This particular case is of special interest, since for $m\in\{2,3,4\}$ it is known to yield the smallest possible value of $\partial_S(A)$ , over all sets $A\subset G$ of given size. We give this classical result a new proof, somewhat different from the standard one. We also give a new, short proof of the Boros-Pales inequality $ω_2(\frac{x+y}2) \le \frac{ω_2(x) + ω_2(y)}2 + \frac12\,|y-x|,$ establish an extremal characterization of the Takagi function as the (pointwise) maximal function, satisfying this inequality and the boundary condition $\max\{ω_2(0),ω_2(1)\}\le 0$ , and obtain similar results for the 3-adic analog $ω_3$ of the Takagi function.

preprint2012arXiv

Solving $a\pm b=2c$ in the elements of finite sets

We show that if $A$ and $B$ are finite sets of real numbers, then the number of triples $(a,b,c)\in A\times B\times (A\cup B)$ with $a+b=2c$ is at most $(0.15+o(1))(|A|+|B|)^2$ as $|A|+|B|\to\infty$ . As a corollary, if $A$ is antisymmetric (that is, $A\cap(-A)=\est$), then there are at most $(0.3+o(1))|A|^2$ triples $(a,b,c)$ with $a,b,c\in A$ and $a-b=2c$ . In the general case where $A$ is not necessarily antisymmetric, we show that the number of triples $(a,b,c)$ with $a,b,c\in A$ and $a-b=2c$ is at most $(0.5+o(1))|A|^2$ . These estimates are sharp.

preprint2011arXiv

The Largest Eigenvalue and Bi-Average Degree of a Graph

We show that for a graph $G$ with the vertex set $V$ and the largest eigenvalue $λ_{\max}(G)$ , letting $M(G) := \max_{X,Y \subset V} \frac{e(X,Y)}{\sqrt{|X||Y|}}$ (where $e(X,Y)$ denotes the number of edges between $X$ and $Y$ ), we have $$ M(G) \le λ_{\max}(G) \le \big(\frac14 \log|V| + 1 \big) \M(G). $$ Here the lower bound is attained if $G$ is regular or bi-regular, whereas the logarithmic factor in the upper bound, conjecturally, can be improved --- although we present an example showing that it cannot be replaced with a factor growing slower than $(\log |V|/\log\log|V|)^{1/8}$ . Further refinements are established, particularly in the case where $G$ is bipartite.

preprint2010arXiv

Kakeya-type sets in finite vector spaces

For a finite vector space $V$ and a non-negative integer $r\le\dim V$ we estimate the smallest possible size of a subset of $V$ , containing a translate of every $r$ -dimensional subspace. In particular, we show that if $K\subset V$ is the smallest subset with this property, $n$ denotes the dimension of $V$ , and $q$ is the size of the underlying field, then for $r$ bounded and $r<n\le rq^{r-1}$ we have $|V\setminus K|=Θ(nq^{n-r+1})$ . This improves previously known bounds $|V\setminus K|=Ω(q^{n-r+1})$ and $|V\setminus K|=O(n^2q^{n-r+1})$ .

preprint2010arXiv

On the size of dissociated bases

We prove that the sizes of the maximal dissociated subsets of a given finite subset of an abelian group differ by a logarithmic factor at most. On the other hand, we show that the set $\{0,1\}^n\seq\Z^n$ possesses a dissociated subset of size $\Ome(n\log n)$; since the standard basis of $\Z^n$ is a maximal dissociated subset of $\{0,1\}^n$ of size $n$ , the result just mentioned is essentially sharp.

preprint2007arXiv

Refined bound for sum-free sets in groups of prime order

Improving upon earlier results of Freiman and the present authors, we show that if $p$ is a sufficiently large prime and $A$ is a sum-free subset of the group of order $p$ , such that $n:=|A|>0.318p$ , then $A$ is contained in a dilation of the interval $[n,p-n]\pmod p$ .

Vsevolod F. Lev

Research overview

Is this your work?

16 publications

The structure of higher sumsets

Zero-sum-free sequences with few subsequence sums

Minimizing the sum of projections of a finite set

Stability result for sets with $3A\ne{\mathbb Z}_5^n$

Symmetric Kneser's Theorem with Trios and $3$ -Transform

Integer sets with identical representation functions

Quadratic residues and difference sets

Discrete norms of a matrix and the converse to the Expander Mixing Lemma

Approximate convexity and an edge-isoperimetric estimate

Flat-containing and shift-blocking sets in $F_2^r$

Edge-isoperimetric problem for Cayley graphs and generalized Takagi function

Solving $a\pm b=2c$ in the elements of finite sets

The Largest Eigenvalue and Bi-Average Degree of a Graph

Kakeya-type sets in finite vector spaces

On the size of dissociated bases

Refined bound for sum-free sets in groups of prime order

See the researcher in context

Building this map preview

Vsevolod F. Lev

Research overview

Is this your work?

16 publications

The structure of higher sumsets

Zero-sum-free sequences with few subsequence sums

Minimizing the sum of projections of a finite set

Stability result for sets with 3A≠Z5n3A\ne{\mathbb Z}_5^n3A=Z5n​

Symmetric Kneser's Theorem with Trios and 333-Transform

Integer sets with identical representation functions

Quadratic residues and difference sets

Discrete norms of a matrix and the converse to the Expander Mixing Lemma

Approximate convexity and an edge-isoperimetric estimate

Flat-containing and shift-blocking sets in F2rF_2^rF2r​

Edge-isoperimetric problem for Cayley graphs and generalized Takagi function

Solving a±b=2ca\pm b=2ca±b=2c in the elements of finite sets

The Largest Eigenvalue and Bi-Average Degree of a Graph

Kakeya-type sets in finite vector spaces

On the size of dissociated bases

Refined bound for sum-free sets in groups of prime order

See the researcher in context

Building this map preview

Stability result for sets with $3A\ne{\mathbb Z}_5^n$

Symmetric Kneser's Theorem with Trios and $3$ -Transform

Flat-containing and shift-blocking sets in $F_2^r$

Solving $a\pm b=2c$ in the elements of finite sets