Enumerating Terry Tao's "parallelograms of primes"

[Jonathan Post]

There are several sequences lurking in Terry Tao's Milliman Lecture I:
Additive combinatorics and the primes

http://terrytao.wordpress.com/2007/12/04/milliman-lecture-i-additive-combinatorics-and-the-primes/#more-220

One comes from his example:

"To give a very simple example of how additive combinatorics can be
applied to the primes, let us consider the problem of finding
parallelograms inside the primes - patterns of the form a, a+b, a+c,
a+b+c with b, c positive integers; for instance, 3, 7, 43, 47 is a
parallelogram of primes. It is very hard to produce any parallelograms
of primes by algebraic means (such as an explicit formula); however,
there is a simple combinatorial argument that shows that such
parallelograms exist in abundance. The only actual information needed
about the primes for this argument is the prime number theorem, which
says that the number of primes less than a large number N is equal to
(1+o(1)) N/\log N in the limit N \to\infty. (Actually, we won't even
need the full strength of the prime number theorem; the weaker
statement that there are \gg N/\log N primes less than N which was
known to Chebyshev and can be established by elementary means based on
the prime factorisation of \binom{2N}{N}, will suffice.)..."

Suppose we generate the infinite number of triples (a,b,c) such that
a, a+b, a+c, a+b+c are all prime.  Sort them on n=a+b+c, and
lexicographically on a, b.

Now, if we have n=prime(k), we enumerate a(k) = how many triples there
are for n=prime(k).

I did this first try entirely by hand, while waiting for my son's car
to be smog checked, so it needs to be checked.

for k = 6, 7, 8, 9, ... I get a(k) = 1,2,4,5,4,7,6,... and a table that begins:
a   b   c   a+b  a+c  a+b+c
3   2   8     5      11      13
3   4   10   7      13      17
7   4    6    11    13      17
3   2   14   5      17      19
5   2   12   7      17      19
5   6   8     11    13      19
11 2   6     13    17      19
3   4   16   7      19      23
5   6   12   11    17      23
7   4   12   11    19      23
7   6   10   13    17      23
13 4   6     17    19      23
5   6   18   11    23      29
7   6   16   13    23      29
7   10 12   17    19      29
11 6   12   17    23      29
3   2   26   5      29      31
3   8   20   11    23      31
5   2   24   7      29      31
5   8   18   13    23      31
11 2   18   13    29      31
11 8   12   19    23      31
17 2   12   19    29      31
3   8   26   11    29      37
5   6   26   11    31      37
5   8   24   13    29      37
7   6   24   13    31      37
11 6   20   17    31      37
11 8   18   19    29      37

Ofr course, Terryv Tao's asymptotics and methods and big picture
context are the whole point, but I'd love to see this table corrected
and extended, and the seq I've identified, to get the ball rolling.

Happy Hanukkah,

Jonathan Vos Post




A109094 looks for a longest path along the edges of the complete graph
with n vertices. Some examples of paths (not necessarily optimum!) that follow
the rules (i) no edge is traveled twice and (ii) the final vertex is not
the starting vertex, in the format n (length): sequence-of-labels :

2 (1): 1-2
3 (2): 1-2-3-1
4 (5): 1-2-3-1-4-2
5 (9): 1-2-3-1-4-2-5-3-4-5-1
6 (13): 1-2-3-1-4-2-5-1-6-3-4-5-6-2
7 (20): 1-2-3-1-4-2-5-1-6-2-7-3-4-5-3-6-4-7-5-6-7-1
8 (24): 1-2-3-1-4-2-5-1-6-2-7-1-8-3-4-5-3-6-4-7-5-6-7-8-2
8 (25): 1-2-3-1-4-2-5-1-6-2-7-1-8-3-4-5-3-6-4-7-5-8-6-7-8-2
9 (35): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-3-4-5-3-6-4-7-3-8-4-9-5-6-7-5-8-6-9
10 (41): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-3-4-5-3-6-4-7-3-8-4-9-5-6-7-8-5
11 (54): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-3-4-5-3-6-4-7-3-8-4-9-3-10
12 (60): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-1-12-3-4-5-3-6-4-7-3-8-4-9
13 (77): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-1-12-2-13-3-4-5-3-6-4-7-3-8-4
14 (83): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-1-12-2-13-1-14-3-4-5-3-6-4-7
15 (104): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-1-12-2-13-1-14-2-15-3-4-5-3
16 (110): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-1-12-2-13-1-14-2-15-1-16-3
17 (135): 1-2-3-1-4-2-5-1-6-2-7-1-8-2-9-1-10-2-11-1-12-2-13-1-14-2-15-1-16-2

The total number of edges is n(n-1)/2. Traveling each at most once
and not allowing return to the starting vertex gives an upper bound
a(n) < n(n-1)/2 for n>2. Heuristically, this seems to be actually achieved for
all odd n, and I presume that there is a "template" path argument to prove
this case looking for some pattern in the paths listed above.

There is also a simple argument why the upper bound is not reached for
cases of even n: the connectivity of each vertex is n-1, an odd number.
Since the path subtracts 2 (an even number) from the connectivity each
time it passes a vertex, for n-2 vertices (all but the first and last)
one edge is not used and remains dangling (as people in surface chemistry
would say). So the additional deficiency in the edge count is (n-2)/2
(at least) for even n, where the division by 2 means that there is one edge
left over for each pair of vertices not connected by an element of the path.

Further brute force search results:
a(18)>=141. a(19)>=170. a(20)>=176. a(21)>=209. a(22)>=215.
a(23)>=252. a(24)>=258. a(25)>=299. a(26)>=305. a(27)>=350. a(28)>=356.
a(29)>=405. a(30)>=411. a(31)>=464. a(32)>=470. a(33)>=527. a(34)>=533.

I am not sure that there is any meaning to finding at least a path
with a(n)=a(n-1)+6 for even n.

Richard Mathar, http://www.strw.leidenuniv.nl/~mathar