Maximal line-free sets in $\mathbb{F}_p^n$
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909899842125824 |
|---|---|
| author | Elsholtz, Christian Führer, Jakob Füredi, Erik Kovács, Benedek Pach, Péter Pál Simon, Dániel Gábor Velich, Nóra |
| author_facet | Elsholtz, Christian Führer, Jakob Füredi, Erik Kovács, Benedek Pach, Péter Pál Simon, Dániel Gábor Velich, Nóra |
| contents | We study subsets of $\mathbb{F}_p^n$ that do not contain progressions of length $k$. We denote by $r_k(\mathbb{F}_p^n)$ the cardinality of such subsets containing a maximal number of elements.
In this paper we focus on the case $k=p$ and therefore sets containing no full line. A~trivial lower bound $r_p(\mathbb{F}_p^n)\geq(p-1)^n$ is achieved by a hypercube of side length $p-1$ and it is known that equality holds for $n\in\{1,2\}$. We will however show that $r_p(\mathbb{F}_p^3)\geq (p-1)^3+p-2\sqrt{p}$, which is the first improvement in the three dimensional case that is increasing in $p$.
We will also give the upper bound $r_p(\mathbb{F}_p^{3})\leq p^3-2p^2-(\sqrt{2}-1)p+2$ as well as generalizations for higher dimensions.
Finally we present some bounds for individual $p$ and $n$, in particular $r_5(\mathbb{F}_5^{3})\geq 70$ and $r_7(\mathbb{F}_7^{3})\geq 225$ which can be used to give the asymptotic lower bound $4.121^n$ for $r_5(\mathbb{F}_5^{n})$ and $6.082^n$ for $r_7(\mathbb{F}_7^{n})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_03382 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Maximal line-free sets in $\mathbb{F}_p^n$ Elsholtz, Christian Führer, Jakob Füredi, Erik Kovács, Benedek Pach, Péter Pál Simon, Dániel Gábor Velich, Nóra Combinatorics 51E21, 11B25, 05D05 We study subsets of $\mathbb{F}_p^n$ that do not contain progressions of length $k$. We denote by $r_k(\mathbb{F}_p^n)$ the cardinality of such subsets containing a maximal number of elements. In this paper we focus on the case $k=p$ and therefore sets containing no full line. A~trivial lower bound $r_p(\mathbb{F}_p^n)\geq(p-1)^n$ is achieved by a hypercube of side length $p-1$ and it is known that equality holds for $n\in\{1,2\}$. We will however show that $r_p(\mathbb{F}_p^3)\geq (p-1)^3+p-2\sqrt{p}$, which is the first improvement in the three dimensional case that is increasing in $p$. We will also give the upper bound $r_p(\mathbb{F}_p^{3})\leq p^3-2p^2-(\sqrt{2}-1)p+2$ as well as generalizations for higher dimensions. Finally we present some bounds for individual $p$ and $n$, in particular $r_5(\mathbb{F}_5^{3})\geq 70$ and $r_7(\mathbb{F}_7^{3})\geq 225$ which can be used to give the asymptotic lower bound $4.121^n$ for $r_5(\mathbb{F}_5^{n})$ and $6.082^n$ for $r_7(\mathbb{F}_7^{n})$. |
| title | Maximal line-free sets in $\mathbb{F}_p^n$ |
| topic | Combinatorics 51E21, 11B25, 05D05 |
| url | https://arxiv.org/abs/2310.03382 |