Simultaneous approximations and covering by arithmetic progressions in \(\mathbb{F}_p\) (Q1841220)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Simultaneous approximations and covering by arithmetic progressions in \(\mathbb{F}_p\) |
scientific article |
Statements
Simultaneous approximations and covering by arithmetic progressions in \(\mathbb{F}_p\) (English)
0 references
16 December 2001
0 references
Let \(A=\{a_1,\dots,a_n\}\subset\mathbb{F}_p\) be a set of residues modulo a prime \(p\). The author formulates the problem of finding the quantity \[ m_n=\max_{|A|=n}\min_{\alpha,\delta}\max_{1\leq i\leq n}\|\delta a_i-\alpha\|, \] where the outer maximum runs over all \(n\)-subset \(A\) of \(\mathbb{F}_p\), \(\alpha,\delta\in\mathbb{F}_p\), \(\delta\neq 0\), and \(\|\delta a-\alpha\|\) denotes the distance from the zero residue. The author proves that this extremal simultaneous approximation problem is essentially equivalent to the combinatorial problem of finding minimal \(l_n\) such that any set of \(n\) residues modulo \(p\) can be covered by an arithmetic progression of length \(l_n\), namely that \(0\leq 2m_n-l_n\leq 1\). One of the main results on \(l_n\) says that if \(p>6^{n-1}/n\) then \[ p^{1-1/(n-1)} (1-np^{-1/(n-1)})<l_n<2n^{-1/(n-1)}p^{1-1/(n-1)}. \] At the expense of a slight relaxation of the coefficients in this estimation a result for any \(p\) and \(n\) is also proved as the second main result. The author conjectures that \[ l_n=2n^{-1/(n-1)}p^{1-1/(n-1)}(1+o(1)) \] for \(n\geq 3\) fixed and \(p\to\infty\). He verifies this for \(n=3\) and \(p\geq 3\) proving that \[ 2\sqrt{p/3}-2\root 4\of{p/3}<l_3<2\sqrt{p/3}. \]
0 references
simultaneous approximation
0 references
finite field
0 references
affine diameter of an \(n\)-element subset of a finite field
0 references
maximum diameter of an \(n\)-element subset of a finite field
0 references
\(n\)-element subset covered by an arithmetic progression
0 references