RUS  ENG
Полная версия
ВИДЕОТЕКА

Дни комбинаторики и геометрии II
16 апреля 2020 г. 17:50, Онлайн-конференция


Erdös-Ginzburg-Ziv problem and Convex Geometry

Д. А. Захаров


https://youtu.be/_iTpIujwl_Q

Аннотация: Let $f(p, d)$ be the minimal number $s$ such that among any $s$ vectors in $\mathbb F_p^d$ one can find $p$ vectors with zero sum.

In [2], we show that for any fixed $d$ and sufficiently large $p$ we have an inequality $f(p,d)\le 4^d p$. This improves the previous bound $f(p,d) < (cd \log d)^d p$ due to [1].

Note that we have a lower bound $f(p, d)\ge 2^d (p-1)+1$ as the example of the hypercube shows. So we have that $f(p,d)$ is an exponential function in $d$ provided that $p>p_0(d)$.

The proof combines various ideas from convex geometry, additive combinatorics and algebraic combinatorics.

[1] Alon Noga and Moshe Dubiner, A lattice point problem and additive number theory, Combinatorica 15.3 (1995): 301-309.
[2] Zakharov Dmitriy, Convex geometry and Erdös-Ginzburg-Ziv problem, arXiv preprint arXiv:2002.09892 (2020).


© МИАН, 2024