78

The primary motivation for this question is the following: I would like to extract some topological statistics which capture how arithmetic progressions of prime numbers "fit together" in a manner that will be made precise below.

Setup

Consider a nested family of simplicial complexes $K(p)$ indexed by prime $p \in \mathbb N$ defined as follows:

  1. the vertices are all odd primes less than or equal to $p$, and
  2. insert a $d$-simplex ($d \geq 2$) spanning $d+1$ vertices if and only if they constitute an arithmetic progression. Of course, one must also insert all faces, and faces-of-faces etc. so that the defining property of a simplicial complex is preserved.

For instance, $K(7)$ has the vertices $3,5,7$ and a single $2$-simplex $(3,5,7)$ along with all its faces. $K(11)$ has all this, plus the vertex $11$ and the simplex $(3,7,11)$. The edge $(3,7)$ already exists so only the other two need to be added. Thus, the fact that $(3,7)$ occurs in two arithmetic progressions bounded by $11$ is encoded by placing the corresponding edge in the boundary of two 2-simplices.

Question

Has someone already defined and studied this complex? What I am mostly interested in is

How does the homology of $K(p)$ change with $p$?

If it helps, here are -- according to home-brew computations -- the statistics for the first few primes (Betti 0 and 1 over $\mathbb{Z}_2$). I've already confirmed that the sequence of Betti-1's is not in Sloane's online encyclopedia of integer sequences. If an intermediate K[p] is missing in the list, that means that the homology is the same as that for the previous prime.

K [3]: 1 0
K [5]: 2 0
K [7]: 1 0
K [13]: 2 0
K [17]: 2 1
K [19]: 1 2
K [23]: 1 4
K [31]: 1 6
K [37]: 2 6
K [43]: 1 7
K [53]: 1 8
K [59]: 1 9
K [61]: 1 10
K [67]: 1 12
K [71]: 1 17
K [73]: 1 20
K [79]: 1 23
K [83]: 1 26
K [89]: 1 31
K [97]: 1 32
K [101]: 1 35
K [103]: 1 41
K [107]: 1 43
K [109]: 1 47
K [113]: 1 53
K [127]: 1 58
K [131]: 1 62
K [137]: 1 67
K [139]: 1 73
K [149]: 1 78

Here's a more concrete question:

Is it true that the $d$-dimensional homology groups of $K(p)$ for $d > 1$ are always trivial?

Vidit Nanda
  • 15,397
  • 4
    "The primary motivation for this question...." Was that a pun? – Gerry Myerson Aug 05 '12 at 22:44
  • 13
    Gerry: sadly, yes. I fear that my sense of humor is progressively deteriorating... – Vidit Nanda Aug 05 '12 at 22:49
  • 2
    This way of constructing complexes must be interesting for sequences of integers other than primes, too! – David Corwin Aug 05 '12 at 22:59
  • 12
    @David: you mean like this? http://arxiv.org/abs/1101.5704 – Vidit Nanda Aug 05 '12 at 23:01
  • Perhaps someone would like to turn the digraph mentioned in this answer http://mathoverflow.net/questions/72040/how-many-sequences-of-rational-squares-are-there-all-of-whose-differences-are-al/72145#72145 into a cell complex? Of course, I'll settle for an answer to the questions instead. Gerhard "Has Complex Around Doing Homology" Paseman, 2012.08.05 – Gerhard Paseman Aug 05 '12 at 23:19
  • Have you computed the distribution of these values for Cramer random primes? One might hope it be similar. 2. Is it clear whether the infinite complex is connected? I guess 2 is disconnected from the odd primes. Are those the only components of the infinite complex? Is it clear for Cramer primes?
  • – Will Sawin Aug 06 '12 at 01:58
  • Will: Sorry, but I don't know what Cramer Primes are, and googling has not yet helped. So the answer to your first question is certainly no. I'm not sure about connectedness (minus that pesky "2"), the only theorem I could think of using is Green Tao and that doesn't seem to help. – Vidit Nanda Aug 06 '12 at 02:15
  • I heard about them in the comments to this mathoverflow question: http://mathoverflow.net/questions/103187/random-pseudoprimes-vs-primes – Will Sawin Aug 06 '12 at 02:46
  • Will: I see. Why do you think this would capture anything of interest in the present context? The second graph in the question that you linked to shows that the count of twin pseudoprimes doesn't even approximate the count of twin primes, and surely twin (blahs) is a degenerate simple case of (blahs) in arithmetic progression... Have I misunderstood? – Vidit Nanda Aug 06 '12 at 02:56
  • 1
    Are the entries with $b_0 = 4$ errors? The vertex 17 in K[17] is connected via 5-11-17, and 41 in K[41] is connected via 17-29-41. – Zack Wolske Aug 06 '12 at 07:14
  • Zack: yeah, that's my mistake. I ran the code up till 997 and only built maximal progressions, so the 5-11-17 didn't get inserted until step 29, thanks to 5-11-17-23-29. I'll re-run once I fix up the code and edit the betti numbers tomorrow. Thanks! – Vidit Nanda Aug 06 '12 at 07:28
  • 1
    @Vel Nias: in contributions to the question mentioned by Will Sawin it is explained or at least hinted at why that specific rand. mod. does not capture this. But, there are other (similar) random models that are widely believed to predict the count of APs of primes. (See eg the intro of the paper of Green-Tao "Linear equations in primes" mentioned there, this is not the paper containing what is typically called the Green-Tao Theorem but a later development.) Perhaps also the following question http://mathoverflow.net/questions/57377/ and things linked from there are interesting for you. –  Aug 06 '12 at 11:09
  • 5
    Regarding connectedness of the inf. complex: if I did not overlook something stupid, it is 'clear' (in the sense that 'everybody' believes it but nobody can prove it) that for any tow odd primes q1,q2 there will be a prime p (indeed infinitely many) such that q1,p and q2,p can each be completed to a 3-AP of primes. In other words for q1,q2 fixed there will be a prime p such that 2p -q1 and 2p -q2 are both prime. More generally any system of linear equations is believed to be solvable 'in the primes', except if there is a 'local' obstruction (congr. or size), and for some this can be shown. –  Aug 06 '12 at 11:32
  • I think there might be another error in your code, or I've misunderstood the construction of "add all faces" (I took it to mean all lower faces, not just the next dimension down). In K[43], 43 is adjacent to 3 (via 3-23-43), and also to 7 and 31 (via 7-19-31-43). 3 is adjacent to 31 (via 3-17-31) and of course to 7, so both (3, 7, 43) and (3, 31, 43) form non-trivial loops, so that $b_1 = 8$, since the 6 loops from K[37] remain in K[43]. It might be that the program is only looking at three term APs, since this is the first place where a 4-AP is necessary. – Zack Wolske Aug 06 '12 at 20:27
  • This might be obvious, but Betti-1 is non-decreasing. If there are three vertices (say $a, b, c$) in $K[m]$ such that each pair is in an arithmetic sequence, but no sequence bounded by $m$ contains all three, then no sequence ever contains all three. The common difference of such a sequence would be a divisor of $\gcd(b-a, c-b)$, and so would contain a subsequence of at least three terms beginning at $a$ and ending at $c$, which would appear in $K[m]$. – Zack Wolske Aug 06 '12 at 20:38
  • This is really cool. I had a look at the Björner paper and didn't quite grok it, so I posted a followup question: http://mathoverflow.net/questions/104149/how-do-facts-about-the-homotopy-type-of-cell-complexes-shed-light-on-analytic-num – Frank Thorne Aug 06 '12 at 21:33
  • My intention with using a random model of primes would be to compare the behavior of the actual primes to the random model. For instance: Is the asymptotic rate of the growth of $b_1$ actually the same, or faster, or slower? – Will Sawin Aug 06 '12 at 21:55
  • Dear Zack, how are you sure that the new cycles created by the introduction of 43 are not related via the boundary of a 2-chain to each other or the old cycles? That is, why are all the 8 cycles you mention in K[43] necessarily non-homologous? In any case, I have modified the question to indicate that not only the codimension-1 facets, but all faces and sub-faces must be inserted into the simplicial – Vidit Nanda Aug 06 '12 at 23:04
  • Ah yes, of course the two I wrote down are homologous, via 3-7-11, 3-11-19, and (the face I neglected) 19-31-43. – Zack Wolske Aug 06 '12 at 23:34
  • On 3-APs see also http://mathoverflow.net/questions/34197/are-all-primes-in-a-pap-3 – Charles Aug 07 '12 at 02:14
  • It seems to me it would make more sense to let your definition do what it says for all d, and put in all edges between vertices (because any pair of primes is an AP.) Then as far as the AP goes, you are in a situation reminiscent of the work of Matt Kahle and his collaborators; a triple of vertices in K(p) is filled in with a 2-simplex with probability about c/p, and he can tell you what the right guess about homology groups is in this case. – JSE Aug 07 '12 at 02:42
  • Jordan: I did toy with that idea but had no clue what the $c$ in your $c/p$ should be. I'm a huge fan of Matt's work, and would love to be able to apply it here. – Vidit Nanda Aug 07 '12 at 03:22
  • If I understand correctly the preceeding discussion, this c is known (or at least knowable) by a classical result of Chowla and Van der Corput on the number of primes in 3-AP. Unfortunately I do not find the actual value with this type of scaling and not sure if I get the rescaling correct on-the-fly. I vaguely believe (but if it is relevant please recheck) it is 1.32.../4 where the 1.32... is the one to be found for example on the slides of Green (page 5 and 6) of his 2006 ICM talk https://www.dpmms.cam.ac.uk/~bjg23/papers/icm-handout.pdf (ADDED: specializing Ex 8, in G&T is another poss.) –  Aug 07 '12 at 11:23
  • Sorry the above constant is off. While I am meanwhile more confident that the count of the 3-APs up to p is about (1.32.../4) p^2/(log p)^3 I took the total numer of 2-simplexes as about (p/log p)^3 [so ordered] but it should be unordered (or so I think) for an extra 1/6 . So then the fraction of 2-simplexes that are present should be c/p with c = (3/2) 1.32... –  Aug 07 '12 at 12:37
  • Quid: thank you for this information. I will run tests to see if the random simplicial complexes have similar statistics and update when I have results. – Vidit Nanda Aug 07 '12 at 15:49