Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.2

Introduction

Easy results

Proof. We prove this by complete induction. The assertion is true when k=1 since 3 is prime. Now consider the set of integers {1, 2, ..., 2k}, and assume that all the sets {1, 2, ..., 2j} have been successfully paired where j is any integer in the range 0 < j < k. We begin by trying to pair 2k with some other number. The possible pairs are (j, 2k) with 0 < j < 2k. The sums of these pairs are all the integers from 2k+1 to 4k-1. Since 2 (2k+1) -2 > 4k-1 Bertrand's Postulate insures that one of these numbers, say 2k+m, is a prime. But m is odd, so the set {m, m+1, ..., 2k-1, 2k} has an even number of elements. This set can be paired so that the sum of the elements in each pair is the prime 2k+m: just pair m+1 with 2k-1, m+2 with 2k-2, etc. The proof is done because our inductive assumption implies that the initial segment from 1 to m-1 can be paired so that the sum of the elements in each pair is a prime. ¤

Definition 1. A sequence of integers {a_k} has the combinatorial Bertrand property (the CB property) if, for all k, the numbers {a₁, a₂, ..., a_2k} can be written as k disjoint pairs so that the sum of the elements in each pair is prime. A integer-valued function f will have the CB property if the sequence {f(k)} has the CB property.

Note. The fact that f(k)=k has the CB property is essentially equivalent to Bertrand's Postulate. For if we know that for every positive integer k, there is m with 0 < m < 2k so that 2k+m is prime, then (taking n = 2k) there must be a prime between n and 2n. A simple adjustment can be made for odd n so a form of Bertrand's Postulate must be true.

What other functions have the CB property? Simple numerical experiments lead to the belief that many functions do or that they have the CB property "eventually". For example, suppose f is a polynomial of degree 1 (f(n)=an+b), and property CB holds. Then f(n)+f(m)= a(n+m) + 2b must be prime infinitely often. By the classical result of Dirichlet on primes in arithmetic progressions this is equivalent to asking that gcd(a,2b) = 1. This Dirichlet condition does not imply the CB property, however: consider the function f(n)=11n+1 and the set of the first 2k values of f when k=1. But such functions most likely eventually satisfy CB.

Definition 2. A sequence of integers {a_k} has the CB property eventually if there is K so that for all k > K, the numbers {a₁, a₂, ..., a_2k} can be written as k disjoint pairs so that the sum of the elements in each pair is prime. An integer-valued function f is eventually CB if the sequence {f(k)} is eventually CB.

We suspect the following result is true:

Conjecture 0. If f(n)= an+b and a and b satisfy the Dirichlet condition gcd(a,2b)=1, then f is eventually CB.

The proof would imitate that of Theorem 1 above. If M(K) is the number of primes less than K of the form ak+b, then M(K) is approximately C K/ (log K) where C is a constant (the reciprocal of the Euler phi function at a). For example, see [E], p. 17, where an error estimate ( O(K exp(-c (log K)^½) with c > 0) is also given. We'd like to apply the proof of Theorem 1 here. Certainly for K large it is easy to see that M(2K) > M(K). Then the numbers {a+1, a+b, a+2b, ..., a+Kb} can be matched up as in the proof of Theorem 1. But the complete induction of Theorem 1 does not immediately apply. Given the evidence at hand, it may possibly be true that we can successfully match some top part of an initial segment of values of f without having enough successful matching to take care of what's left. That is, consider the set {f(1), f(2), ..., f(2K)}. Certainly for K large we can find j odd with f(j)+f(2K) prime. Then the set {f(j), f(j+1), ..., f(2K)} can be divided into pairs whose sums are prime and all the same: f(j)+f(2K). But j could be small, and the set {f(1), f(2), ...,f(j-1)} could perhaps not be successfully matched into pairs whose sums are prime. We thank Professor Andrew Granville for pointing out this difficulty. Either better asymptotics are needed or a better proof! In specific cases, such as f(n)=3n+1 it seems apparent that some initial computation plus constants known well enough can establish the eventual CB property.

Probabilistic analysis and experimental evidence

"Theorem 2". The probability that the set {1², 2², ..., (2k)²} can be broken up into k pairs so that the sum of the elements of each pair is a prime approaches 1 as k approaches infinity.

"Proof". The Prime Number Theorem states that there are about K/(log K) primes less than or equal to K. Thus the chance that t randomly selected integers in the range [1,K] are prime is approximately (log K)^-t. If we fix a positive integer k, and try to find a pairing of the set{1², 2², ..., (2k)²}, then K= 4k^2 and t=k. The expectation of success will be enhanced since we can try all possible pairings of the set, and there are (2k)!/ (2^kk!) such pairings. Thus we will expect success if the limit as k tends to infinity of (log (4k^2))^-k( (2k)!/ (2^kk!)) is at least 1. This can be verified by replacing the factorials using Stirling's formula. The condition above then reduces to showing that 2^½(2k/e)^k(log(8k²)^-k is at least 1. This is true since log growth is slower than polynomial growth. ¤

Comments. The use of the quotes (" and ") in both the Theorem and the Proof above is certainly justified, since both the statement and the verification are more approximate than precise. What is really shown is that any sequence with at most, say, polynomial growth (such as k²), will have "the CB property" relative to a "sparse" sequence such as the primes. We have implicitly made assumptions about uniform distribution and independence which are not valid here. First, the sums of the elements in each pair are far from random relative to the primes (e.g., the function f(k)=2k² would give a sequence with the same asymptotic properties, but of course every sum f(k)+f(j) would be composite). Secondly, both the primes and the squares are not uniformly distributed. There are more "small" primes than there should be, and the squares are more concentrated in the lower portion of their range. This coincidence may in fact aid in obtaining successful pairings. Third, unlike what is understood in the "Proof", there is substantial dependence among the possible sets of pairings and their primality. For example, 3²+4² is not prime, and thus any collection of pairings which included (3,4) in its list could not be successful. All these remarks apply to any polynomial function. In the case of f(k)=k² there is an additional obstacle, due to Fermat and Euler, to the analysis above, which implicitly assumes independence: only primes of the form 4m+1 can be written as the sum of two squares, and each such prime can be so written in exactly one way (up to order). Thus if (4,1) is used as one pair, no other pair summing to a prime of the form 4m+1 which can be written as k²+1 (e.g., 37) can be used in the "dissection" of {1², 2², ...,(2k)²}. So there is more complex dependence than the "Proof" allows.

In spite of the above objections, experimental evidence shows that there are far more successful pairings than predicted by the rough probabilistic "Proof" above. Below is a table of what happens for k between 1 and 10 in both the linear (f(k)=k) and quadratic (f(k)=k^2) cases. We give the "expected" number of successful complete pairings predicted using a Stirling's formula approximation (for the quadratic case as in the "Proof" above, and for the linear case with K=4k). We show the number actually observed. For background, we also present the total number of possible complete pairings (our probabilistic universe) in each case.

We cannot explain the interesting large discrepancies in the figures above.

It is possible to obtain functions which are far from having the CB property but which also have pairwise relatively prime values.

Theorem 3. There exist injective integer-valued functions f with gcd(f(i), f(j)) = 1 for all positive integer i and j, and such that f(i)+f(j) is composite for all positive integer i and j.

Proof. We give a simple "lacunary" construction of one such function. First, for each integer K we construct an integer-valued function g_K which signals K-long segments of composite integers. Namely, take g_K(t)= (K+1)! t + 1. Then for every K and t, gcd(s,g_K(t)) =1 for s between 1 and K. Also, g_K(t)+s is composite for such s. In order to obtain a function satisfying the theorem, merely assume that f(1), f(2), ..., f(m) have already been defined. We can also assume that f(1) < f(2) < ... < f(m). Take K=f(m), and define f(m+1) = g_K(1).

Note. The (non-unique) function created in the theorem is increasing. For example, if we begin by assuming f(1)=1 then f(2)=3, f(3)=7, f(4)=5 041 and f(5) is approximately 10^{16 480}. So f is very rapidly increasing. Are there simple functions with slower growth which satisfy the conclusions of this theorem? The probabilistic assertions of "Theorem" 2 do not apply to the functions constructed here because of their rapid growth.

Conjectures

Conjecture 1. Suppose f is a polynomial with integer coefficients which is positive for positive k. Then f has property CB eventually if and only if f(k)+f(j) is an irreducible polynomial in two variables and f(k)+f(j) has content 1.

"Content" here means the gcd of the coefficients of a polynomial, and is the natural generalization of the Dirichlet condition of Conjecture 0. Certainly the conditions of this Conjecture are necessary, and the probabilistic analysis of "Theorem" 2 makes it natural to hope that they are sufficient. Of course the CB problem can be restated as a graph-coloring problem, where the nodes are the integers {1, 2, ..., 2k}, and two nodes k and j are connected by an edge exactly when f(k)+f(j) is prime. This seems to offer no enlightenment, but does lead to a somewhat generalized conjecture. We could put in edges where other functions are prime (e.g., k² + kj + j²), or we can even investigate more general examples (analogous to directed graphs). Namely, we can study any polynomial in two variables, rather than one which is symmetric in its two variables. Then the CB property itself will lose some symmetry, but here is one possible generalization:

Conjecture 2. Suppose p(k,j) is a polynomial in two variables with integer coefficients, and p is irreducible with content 1. If n is sufficiently large, then the set {1, 2, ..., 2n} can be arranged into n disjoint pairs so that if (a,b) is one pair, either p(a,b) or p(b,a) is prime.

Numerical experiments with several polynomials (e.g., k+j², k²+j³, and k²+kj+j²) have been done. The experiments seem to support the conjecture.

We can further generalize by looking at "higher order" versions of the CB property:

Definition 3. Suppose N is a positive integer. A sequence of integers {a_k} has the N^th order combinatorial Bertrand property (the N^th order CB property)} if, for all k, the numbers {a₁, a₂, ..., a_Nk} can be written as k disjoint sets of N elements so that the sum of the elements in each set is prime.

One can make obvious generalizations to fit the phrases: a function has the N^th order CB property or a sequence (or function) has the N^th order CB property eventually. When N = 1, such sequences have to be subsequences of the primes. A simple conjecture which we are unable to verify is the following:

Conjecture 3. The sequence of odd integers {1, 3, 5, ... } has the third order CB property eventually.

Again, probabilistic reasoning coupled with the obvious necessary conditions applied here to the polynomial 2 (k + j + i) + 3 seem to suggest the truth of Conjecture 3.

A additional natural collection of sequences to study for CB behavior would be sequences defined by simple linear recursions. For example, consider the sequence defined by the following recursion and initial condition: a_n+1 = 2 a_n + 1 with a₁ = 1.

This recursion can be solved explicitly to obtain a_n = 2ⁿ -1. Does this sequence have the third order CB property? Here the probabilistic reasoning does not apply because of the growth of {a_n}. But the sequence is on the borderline probabilistically. Deciding if such exponentially growing sequences are eligible seems to need more information than we have.

On the other hand, functions with finite range are also of interest. In trying to determine how many distinct functions with finite range there are which have the N^th order CB property, we come across the following extremal problem:

Problem 1. Suppose S and T are positive integers. Find a set of integers {a₁, ..., a_S} with the maximum number of T element subsets which sum to a prime. What is this number and this set?

Is an initial segment of the integers such an extremal set?

These questions all seem to be difficult because even the simplest non-linear case (does f(k)=k² have the CB property?) approaches the limits of current knowledge. For example, it is not known if there are infinitely many prime numbers of the form k² +1 (see the discussion in the Appendix to [HW]). While this question may be independent of the CB property for this f, its difficulty does not suggest that the proof of the CB property for this f will be immediate.

Finally, we have a question about algorithms. Suppose we're given an integer-valued function, f. How can we check if some initial values of f have the CB property? Since the number of pairs to be checked is very large, any way to shrink this number is worth considering. It is disconcerting to report that a sort of Greedy Algorithm seems to work even when there is no justification. The Greedy Algorithm is motivated by the proof of Theorem 1. Suppose f is increasing (e.g., f(k)=k or f(k)=k²). In order to check pairs in the set { f(1), f(2), ..., f(2n)}, first find a match for the largest element (if possible). That is, find j between 1 and 2n so that f(j)+f(2n) is prime. Remove f(j) and f(2n) from the list and continue, again trying to match the largest element. Continue matching elements and removing pairs in this fashion as long as possible. We'll say that the Greedy Algorithm is successful if this procedure results in the empty set. Of course the Greedy Algorithm reduces verifying property CB to an O(n²) number of prime checks (a large reduction from the indicated number!). The Greedy Algorithm need not be successful (a simple example is the list {1,8,9,10}, where the algorithm grabs 9 and 10 and is left with 1+8=9, and doesn't find {1,10} and {8,9}).

The proof of Theorem 1 shows that the Greedy Algorithm must be successful for f(k)=k. However, the Greedy Algorithm has been successful in every example we have checked for f(k)=k². It does not seem to work with some other polynomials. If f(k,j) = k² +k j + j², the number of pairs to be checked seems to grow very quickly with n (e.g., when n = 20, we needed to check 213 347 331 pairs).

Problem 2. Is the Greedy Algorithm always successful for f(k)= k²?

It is possible that we've just been lucky because there are many coincidences for small numbers.

Bibliography

(This is the source for sequences A000341 and A000348 .)

Written October 1991; revised December 1997; published in Journal of Integer Sequences Jan. 1, 1998.