Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.03650 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912521647030272 |
|---|---|
| author | Dean, Christian Havard, Haley Hawkins, Elizabeth Heard, Patch Lott, Andrew Rice, Alex |
| author_facet | Dean, Christian Havard, Haley Hawkins, Elizabeth Heard, Patch Lott, Andrew Rice, Alex |
| contents | We explore from several perspectives the following question: given $X\subseteq \mathbb{Z}$ and $N\in \mathbb{N}$, what is the maximum size $D(X,N)$ of $A\subseteq \{1,2,\dots,N\}$ before $A$ is forced to contain two distinct elements that differ by an element of $X$? The set of forbidden differences, $X$, is called \textit{intersective} if $D(X,N)=o(N)$, with the most well-studied examples being $X=S=\{n^2: n\in \mathbb{N}\}$ and $X=\mathcal{P}-1=\{p-1: p\text{ prime}\}$. In addition to some new results, including exact formulas and estimates for $D(X,N)$ in some non-intersective cases like $X=\mathcal{P}$ and $X=S+k$, $k\in \mathbb{N}$, we also provide a comprehensive survey of known bounds and extensive computational data. In particular, we utilize an existing algorithm for finding maximum cliques in graphs to determine $D(S,N)$ for $N\leq 300$ and $D(\mathcal{P}-1,N)$ for $N\leq 500$. None of these exact values appear previously in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_03650 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Notes and computations on forbidden differences Dean, Christian Havard, Haley Hawkins, Elizabeth Heard, Patch Lott, Andrew Rice, Alex Number Theory Combinatorics We explore from several perspectives the following question: given $X\subseteq \mathbb{Z}$ and $N\in \mathbb{N}$, what is the maximum size $D(X,N)$ of $A\subseteq \{1,2,\dots,N\}$ before $A$ is forced to contain two distinct elements that differ by an element of $X$? The set of forbidden differences, $X$, is called \textit{intersective} if $D(X,N)=o(N)$, with the most well-studied examples being $X=S=\{n^2: n\in \mathbb{N}\}$ and $X=\mathcal{P}-1=\{p-1: p\text{ prime}\}$. In addition to some new results, including exact formulas and estimates for $D(X,N)$ in some non-intersective cases like $X=\mathcal{P}$ and $X=S+k$, $k\in \mathbb{N}$, we also provide a comprehensive survey of known bounds and extensive computational data. In particular, we utilize an existing algorithm for finding maximum cliques in graphs to determine $D(S,N)$ for $N\leq 300$ and $D(\mathcal{P}-1,N)$ for $N\leq 500$. None of these exact values appear previously in the literature. |
| title | Notes and computations on forbidden differences |
| topic | Number Theory Combinatorics |
| url | https://arxiv.org/abs/2508.03650 |