Using ordered pairs and sequences to give a required condition for any counter-example to Legendre's Conjecture

Question

I found it very challenging to write this question. I apologize for any ambiguity.

This is an argument that I am working on related to Legendre's Conjecture. I appreciate any questions or any corrections. :-)

Let:

• $x > 1$ be an integer
• $T(x)$ be the set of primes $p$ such that $0 < p < x$ and $p \nmid x(x+1)$
• $|T(x)|$ be the count of elements in $T(x)$
• $S_{T(x)}$ be a set of ordered pairs $(p_i,p_j)$ with the following properties:

• $p_i \ne p_j$
• $x^2 + x - p_i \equiv 0 \pmod {p_j}$
• $p_i,p_j \in T(x)$

Definitions:

• A sequence of primes $(p_1, p_2, p_3, p_4, \dots )$ is constructible from $S_{T(x)}$ if the following:

• the first element $c$ in the sequence can be any prime such that $c \in T(x)$
• the next element $n$ can be any prime where the ordered pair $(c,n) \in S_{T(x)}$
• the sequence consists of $2$ or more elements where for each $(p_i,p_{i+1})$, it follows that $(p_i,p_{i+1}) \in S_{T(x)}$ and for each $(\dots,p_j,p_{j+1}. \dots)$, it follows that $(p_j,p_{j+1},\dots) \in S_{T(x)}$

• The set $S_{T(x)}$ is said to have repeats if a sequence is constructible that includes a prime more than once.

Example 1: $x=16, T(x)=\{3,5,7,11,13\}, S_{T(x)} = \{ (5,3), (7,5), (11,3), (13,7) \}$

In this example, $S_{T(x)}$ does not have repeats

Example 2: $x=31, T(x)=\{3,5,7,11,13,17,19,23,29\}, S_{T(x)} = \{ (3,23), (5,3), (5,7), (7,5), (11,3), (13, 11), (17,3), (17,5), (17,13), (19,7), (23,3), (23,17), (23,19), (29,3) \}$

In this example, $S_{T(x)}$ has repeats since the sequence $(3,23,3)$ is constructible from $S_{T(x)}$.

Claim: If a counter example exists to Legendre's Conjecture for a given $x$, the set of ordered pairs $S_{T(x)}$ will necessarily have repeats.

(1) Assume that for each $p \in T(x)$, there exists a $q \in T(X)$ such that $(p,q) \in S_{T(X)}$ [If this were not true, $x^2 + x - p$ would necessarily be a prime.]

(2) Let $n = |T(x)|$ be the number of elements in $T(x)$.

(3) We can arbitrarily order each $p \in T(x)$ up to $p_{n-1}$ in the following way:

• $p_1 = $ the least prime in $T(x)$.
• For each prime $p_i$, let $p_{i+1}$ be any prime where $(p_i,p_{i+1}) \in S_{T(x)}$ and $p_{i+1}$ has not yet been assigned an order. [If it has already been assigned an order, then we have a repeat]
• Assume that we do not run out of primes (otherwise, we have reached a repeat and the argument is proven)

(4) At $p_n$, there is no remaining unordered primes. Since, by assumption, there exists $p_i \in T(x)$ such that $(p_n,p_i) \in S_{T(x)}$, it follows that there must be a repeat.

Does this argument hold?

Thanks.

---

Edit:

Great comment from John Omielan. I have made changes to make the question less confusing.

• Added a definition for $x$
• Removed $2$ from examples since $2 | x^2 + x$ so it will never be an element of $T(x)$.
• Changed $p_1$ to $p_4$ in the definition of constructible to avoid any confusion.
• Add a specific $x$ value for the first example
• Removed some redundancies in the definition of $S_{T(x)}$
• Modified the title to make my question clearer.
• Updated Example 2 to make it complete
• Updated the third point in definition of constructible

Answer 1

In your Definitions: section, you wrote:

• A sequence of primes $(p_1, p_2, p_3, p_4, \dots )$ is constructible from $S_{T(x)}$ if the following:

• the first element $c$ in the sequence can be any prime such that $c \in T(x)$
• the next element $n$ can be any prime where the ordered pair $(c,n) \in S_{T(x)}$
• the sequence consists of $1$ or more elements where the first element in the sequence meets the first condition and all other elements meet the second condition.

---

I found this quite confusing. Your third point states the sequence consists of $1$ or more elements. However, your second point requires there to be at least $2$ elements. Also, the last part of the third point says "all other elements meet the second condition". However, the second condition uses $c$, which is defined in the first condition for the first element. This seems to imply all of the other elements, say $p_i$, must have $(p_1,p_i) \in S_{T(x)}$. However, your second example stating $(3,23,3)$ is constructible shows this is not the case.

Instead, from the context used later in your Claim, it seems the definition can be just simply stated as:

• A sequence of $n \ge 2$ primes $(p_1, p_2, p_3, \dots, p_n)$ is constructible from $S_{T(x)}$ if $(p_i, p_{i+1}) \in S_{T(x)} \; \forall \; 1 \le i \le n - 1$.

Assuming this is what you mean, then regarding your Claim, any counter-example to Legendre's conjecture would not have any prime $p_L$ where $x^2 \lt p_L \lt x^2 + x$, although the claim itself is for $x^2 \lt p_L \lt x^2 + 2x + 1$. As such, your first part $(1)$ must hold since, as you state, otherwise if it did not, then $p_L = x^2 + x - p$ must be a prime. This is because if it were composite, it would have at least $2$ factors, with the smaller one being less than $x$. Any prime factor of this smaller factor can't divide $x^2 + x$ (if it did, then it must also divide $p$), so it must be in $T(x)$.

The rest of your Claim only depends on your part $(1)$ since, using it, you can create an unlimited length chain of primes in multiple ways (the rest of your claim gives one method, although note $p_1$ can actually be chosen to be any prime, not necessarily the smallest one) that, since there are only a finite number of primes in $T(x)$, must eventually repeat.

In conclusion, your stated Claim is true.