Does a counter example exist where no prime is found given the following conditions...

Question

Let:

• $x>1$ be an integer
• $y$ be an even integer with $2x \le y \le x(x+1)$
• gcd$(a,b)$ be the greatest common divisor of $a$ and $b$
• $U(x,y)$ be the set of integers $u$ such that $0 < u \le x$ and gcd$(u,y)=1$

Does it follow that for any $x$ and any $y$ that meets the above criteria, there always exists $u \in U(x,y)$ such that either $y-u$ or $y+u$ is prime?

I found that this is not the case if I only consider $y-u$.

For example:

• $U(11,126) = \{ 1, 5, 11\}$ and none of these are primes: $\{ 125, 121, 115\}$

Answer 1

This is an interesting conjecture. Although I've seen several conjectures stating at least one prime exists among a certain length of consecutive integers starting from some defined value, I don't recall any other conjectures where the starting point can roam in a certain range.

Regarding your minimum required conditions, it's also not the case if you only use $y + u$. Starting from the opposite side of your example, if $x = 11$ and $y = 114$, then since $113$ and $127$ are consecutive primes, there's no prime between $y = 114$ and $y + x = 125$. In particular, since $114 = 2\times 3 \times 19$, you have $U(11, 114) = \{1, 5, 7, 11\}$ giving $y + u \in \{115, 119, 121, 125\}$. Nonetheless, I believe if you limit $x$ to larger values only, i.e., $x \ge x_0$ for some integer $x_0$ (I suspect even just $12$ will do), then only one of $y - u$ or $y + u$ would then be sufficient.

Apart from the special case where $y = 2x$ and $x$ is prime (with Bertrand's postulate ensuring there's at least one other prime between $x$ and $2x$), all other primes of the form $y \pm u$ must have $\gcd(u, y) = 1$, so your conjecture is basically asking if there's at least one prime in $[y - x, y + x]$.

Your range for $y$ is great for checking among the values of a specific $x$, but if you're methodically looking for a counter-example by checking all $y$ for each next $x$ value, then there'd be a lot of duplication. Since if there's no prime in $[y - x, y + x]$ for any given $x$ means there's obviously none for any smaller $x$, you don't need to check any $y$ which has already been used with a smaller $x$. As such, you can reduce the ranges for $y$ so it's then just $2x \le y \le x(x + 1)$ for $x = 2$, and $(x - 1)x \lt y \le x(x + 1)$ for $x \gt 2$.

Using these reduced ranges of $y$ values for $x \gt 2$, then $[y - x, y + x]$ includes all of $[(x - 1)x, x^2]$ and/or $[x^2, x(x + 1)]$. Note Oppermann's conjecture, which states there's at least $1$ prime in each of those $2$ regions, is a somewhat stronger version of your conjecture. As for checking this conjecture, the Status section states

Even for small values of $x$, the numbers of primes in the ranges given by the conjecture are much larger than $1$, providing strong evidence that the conjecture is true.

Regarding a range where this has actually been checked, in Strong Version of Andrica’s Conjecture, section "$2$ Verifying strong Andrica for primes $p \lt 2^{64}$" explains how the maximal prime gap data up to $2^{64}$ shows it's true up to that value. Then section "$3$ Verifying Oppermann for primes $p \lt 2^{64}$ (and integers $m \lt 2^{32}$)" states and proves its theorem $3.1$, i.e.,

The strong Andrica conjecture implies the Oppermann conjecture.

Thus, as Oppermann's conjecture is confirmed for $x$ up to $2^{32}$, so is your conjecture to that point. Note I also suspect the same prime gaps data which was used will also show just one of $y - u$ or $y + u$ is sufficient if $x$ is large enough, as I suggested earlier.

One final thing I noticed about your conjecture is the specific case where $y = x(x + 1)$ is basically Legendre's conjecture. However, apart from possibly providing a counter-example, anything related to Legendre's conjecture may not be of much specific use to you since your conjecture is stronger than it.