Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2409.07442 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910600020361216 |
|---|---|
| author | Bukh, Boris van Hintum, Peter Keevash, Peter |
| author_facet | Bukh, Boris van Hintum, Peter Keevash, Peter |
| contents | We consider two questions of Ruzsa on how the minimum size of an additive basis $B$ of a given set $A$ depends on the domain of $B$. To state these questions, for an abelian group $G$ and $A \subseteq D \subseteq G$ we write $\ell_D(A) \colon =\min \{ |B|: B \subseteq D, \ A \subseteq B+B \}$. Ruzsa asked how much larger can $\ell_{\mathbb{Z}}(A)$ be than $\ell_{\mathbb{Q}}(A)$ for $A\subset\mathbb{Z}$, and how much larger can $\ell_{\mathbb{N}}(A)$ be than $\ell_{\mathbb{Z}}(A)$ for $A\subset\mathbb{N}$. For the first question we show that if $\ell_{\mathbb{Q}}(A) = n$ then $\ell_{\mathbb{Z}}(A) \le 2n$, and that this is tight up to an additive error of at most $O(\sqrt{n})$. For the second question, we show that if $\ell_{\mathbb{Z}}(A) = n$ then $\ell_{\mathbb{N}}(A) \le O(n\log n)$, and this is tight up to the constant factor. We also consider these questions for higher order bases. Our proofs use some ideas that are unexpected in this context, including linear algebra and Diophantine approximation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07442 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Additive Bases: Change of Domain Bukh, Boris van Hintum, Peter Keevash, Peter Number Theory Combinatorics 11B13, 05B10, 20K27 We consider two questions of Ruzsa on how the minimum size of an additive basis $B$ of a given set $A$ depends on the domain of $B$. To state these questions, for an abelian group $G$ and $A \subseteq D \subseteq G$ we write $\ell_D(A) \colon =\min \{ |B|: B \subseteq D, \ A \subseteq B+B \}$. Ruzsa asked how much larger can $\ell_{\mathbb{Z}}(A)$ be than $\ell_{\mathbb{Q}}(A)$ for $A\subset\mathbb{Z}$, and how much larger can $\ell_{\mathbb{N}}(A)$ be than $\ell_{\mathbb{Z}}(A)$ for $A\subset\mathbb{N}$. For the first question we show that if $\ell_{\mathbb{Q}}(A) = n$ then $\ell_{\mathbb{Z}}(A) \le 2n$, and that this is tight up to an additive error of at most $O(\sqrt{n})$. For the second question, we show that if $\ell_{\mathbb{Z}}(A) = n$ then $\ell_{\mathbb{N}}(A) \le O(n\log n)$, and this is tight up to the constant factor. We also consider these questions for higher order bases. Our proofs use some ideas that are unexpected in this context, including linear algebra and Diophantine approximation. |
| title | Additive Bases: Change of Domain |
| topic | Number Theory Combinatorics 11B13, 05B10, 20K27 |
| url | https://arxiv.org/abs/2409.07442 |