## Friday, 20 July 2012

### A modular problem page 2

I can go some way to generalising the proof I made for 3 factor numbers to numbers with more factors. For instance:

A number has 4 odd prime factors a < b < c < d

Assume
abc = 1 mod d = (0, 0, 0, 1)
abd = 1 mod c = (0, 0, 1, 0)
acd = 1 mod b = (0, 1, 0, 0)
bcd = 1 mod a = (1, 0, 0, 0)

abc + abd + acd +bcd = (1, 1, 1, 1)

Subtract 1

= (0, 0, 0, 0) = 0 or abcd

a >= 3, b >= 5, c >= 7, d >=11

abc =< abcd/11
abd =< abcd/7
acd =< abcd/5
bcd =< abcd/3

1/3 + 1/5 + 1/7 + 1/11 = 886/1185

abcd = 1185

Therefore (1, 1, 1, 1) ≠ abcd + 1

abc + abd + acd +bcd = 1

RAA

Therefore the initial assumption was impossible.

It looks to me as though this works up to 8-factor numbers (and would have worked for 3 factor numbers) but then stops working because 1/3 + 1/5 + .... 1/ 23+ 1/29 > 1 (29 being the 9th odd prime).
A number has 4 odd prime factors a < b < c < d
Also, if this works at all, then it works for any number with an odd number of factors, for instance for five factors:

abcd + abde + abce +abde + bcde = (1, 1, 1, 1, 1)

Subtract 1

= (0, 0, 0, 0, 0) = 0 or abcde

However abcde+1 is even, and (abcd + abde + abce +abde + bcde) is odd.

so abcde+1 ≠ (abcd + abde + abce +abde + bcde)

(Actually this last bit isn't completely sound - if abcd + abde + abce +abde + bcde = 1 mod abcde but this is a multiple of abcde rather than abcde itself, then the proof doesn't hold - but this at least extends the proof to numbers with a very large number of odd factors since it takes a long time to reach 2 in the series 1/3 + 1/5 + 1/7  + 1/11.... However this series isn't convergent, so you do eventually get to 2)

CRGreathouse also commented that

"You can extend it to 9- or even 10-factor numbers by adding finite checking. Probably too difficult for more than 9 factors if you're doing it by hand, though."
Which is correct - there would be many combinations for 9, 10 and above where the fractions didn't exceed 1, so it does work in theory for a big swathe of highly composite numbers - you just can't make it a general proof without finite checking.

### A modular problem

This is something I already put up on My Math Forum.

Let a, b, c be three different prime numbers.

Is it possible that

ab = 1 mod c
ac = 1 mod b
bc = 1 mod a

This is clearly possible if one of the numbers is even as 30 is an example:

6 = 1 mod 5
10 = 1 mod 3
15 = 1 mod 2

But is it possible if they are all odd?

abc has three prime factors, a < b < c
Each number below abc has a unique set of modular residues for a, b, c which we will express as (x, y, z)

Assume
ab = 1 mod c
ac = 1 mod b

Start at (0, 0, 0) = 0
First we add (0, 0, 1) to get ab = 1 mod c = (0, 0, 1)
Then we add (0, 1, -1) to get to ac = 1 mod b = (0, 1, 0)

Now, assume we add (0, 1, 0) + (-1, -1, 0) = (-1, 0, 0)

If (-1, 0, 0)= bc then bc ≠ 1 mod a

We know that (-1, -1, 0) < bc because
(0, 0, 1) = ab
(-1, -1, 0) = (0, 0, 1) – 1 = ab - 1
ab < bc
Therefore (-1, -1, 0) < bc

Is it possible that (-1, 0, 0) ≠ bc?

To get to any other value of (x, 0, 0) we must add or subtract a multiple of bc from (-1, 0, 0)

We can’t subtract because (-1, 0, 0) < bc.

And (-1, 0, 0) + bc > bc.

Therefore (-1, 0, 0) = bc

Therefore bc ≠ 1 mod a

C.R.Greathouse helpfully pointed out that since I hadn't clearly specified that a, b, and c were odd that last bit didn't work - there's a bit more detail on how that can be cleaned up here.

What I really want is a more general version of this proof, that applies to numbers of more than three factors, as that would fit in with the other stuff I've been working on. I've made a start on this here.

## Tuesday, 17 July 2012

### A simpler thought on twin primes

C.R.Greathouse from My Math Forum has succeeded in convincing me I was either wrong or overcomplicating things (or just being a crank...) in a few previous posts, which I've taken down for now. The "stretching and merging" created some problems, at the very least it made it pretty hard to conceive of how individual substitutions of numbers actually affect the pattern.

This is a simplified approach, which doesn’t depend on any stretching or merging - I'm not offering it as a proof, but to try and communicate the bit I find interesting and see if there is any way to improve this.

Again, this is based on the idea of numbers laid out in a hypercuboid.

In the diagrams above I am just colouring any pn plane other than (p^2)n+p black and any pn+2 plane other than (p^2)n+p+2 black. Every number starts out white. Once a number is black it stays black.

(I’ve started from the point where even numbers are already coloured black) - the 49n grid is incomplete but I hope there is enough for clarity.)

We leave the (p^2)n+p plane and the (p^2)n+p+2 plane white (except where they are intersected by a black plane).

I would like to argue that:

Every number will end up white or black. Any number >3 that ends up white is a twin prime. If there is an infinitude of white squares in this pattern (once it has been continued infinitely) then there is an infinitude of twin primes.

This seems counter-intuitive because we are doing nothing to mark how the (p^2)n+p numbers intersect with the (p^2)n+p+2 numbers. I believe we don’t need to because any number >3 that doesn’t end up black in this grid must be on both a (p^2)n+p plane and  a (p^2)n+p+2 plane, and can’t be on more than one of each.

However, for this to hold, I do have to make an assumption :

Let a, b, c be three different odd prime numbers.
Assume it is not possible that
ab = 1 mod c
ac = 1 mod b
bc = 1 mod a

(I've proved this bit here.)

(This is possible if one of the numbers is even as 2, 3, 5 is an example: 6 = 1 mod 5, 10 = 1 mod 3, 15 = 1 mod 2).

We also need to assume the same principle for numbers with more factors, for instance for 4 factors, assume that it is not possible that
abc = 1 mod d
abd = 1 mod c
acd = 1 mod b
bcd = 1 mod a

I've proved this for up to 8 factors and for any number with an odd number of factors here. But it is still a big assumption to assume it holds for all numbers.

That rather big assumption has an interesting consequence.

If true, I think it means we don’t have to worry about how the (p^2)n+p plane and (p^2)n+p+2 planes intersect in the grids above. Which means that this is a simpler and more effective sieving process than it might look on first sight. Here's why:

For an odd composite number X to appear on a (p^2)n + p plane, it must be expressible as p(pn+1).

This means that the product of the prime factors of X other than p must be expressible as pn+1.In other words if the factors are a and b, a = 1 mod b.

For a number with two odd factors, for instance 3 x 13, it is clearly impossible that
a = 1 mod b
b = 1 mod a

So any composite number with two odd factors is on at least one black plane. (For instance 39 is on the 169n+39 black plane, 9 is on the 9n black plane.)

And if the assumption above about 3+ factor numbers is true then any number that is on more than one (p^2)n + p plane is on at least one black plane.

The same also holds for any number on more than one (p^2)n + p + 2 plane (for the same reason, as this is also dependent on the factors of (p^2)n + p.)

So any number which isn't on a black plane is on only one (p^2)n + p plane and only one (p^2)n + p + 2 plane, and is thus a twin prime.

I find this interesting because rather than looking at the interaction between two patterns (pn and pn+2) we only need to look at the one pattern.

Now, what I was previously trying to do is to find a tricksy way to show that the pattern of intersections between the black planes is topologically equivalent in this grid and in the prime one where we don’t eliminate any pn+2 planes. But doing it with “duplicating and/or merging” creates other problems as Mr Greathouse patiently prodded me towards seeing.

However, it still seems to me that the situation in the grid above has some kind of topological equivalence to the situation in the prime grid. In each dimension we simply take a black slice through part of the hypercuboid –  the black slices are just wider in the twin version.

(For instance, on a really basic topological level - imagine we rearranged each dimension with the black planes in the middle and the white ones on either side, like this:

There is no logical reason we can't do that as we aren't losing any numbers and can rearrange the planes in the same order in each version. Then we could physically widen (without duplicating) the white planes and narrow (without deleting) the black planes in the twin version of the image (top) and end up with the same area of the cross section being coloured black or white as on the prime version (bottom) - this wouldn't give us any more or less numbers in the white and black areas, but it would be one way of bringing out the topological similarity (- it's a damn sight closer than a doughnut and coffee mug, at least).

I know it wouldn't be fair to assume that a process of this sort necessarily leads to an infinitude of gaps, but we do already know that in the prime version it does leave an infinitude of gaps.

So 1) is the assumption above correct for 8+factor numbers and 2) is it fair therefore to assume that there is an infinitude of gaps in this pattern? If not, there's probably not a way forward... I wonder if there is a more precise, formal way to look at the topological equivalence question though?

## Monday, 16 July 2012

### Plane substitutions.

OK, to help explain the logic of the attempted twin prime proof, here is an example of how the plane substitutions work. Here's the starting point of the 4n x 9n grid (in other words how it looks in the prime number hypercuboid we started from).
 4n 4n+1 4n+2 4n+3 9n 36 9 18 27 9n+1 28 1 10 19 9n+2 20 29 2 11 9n+3 12 21 30 3 9n+4 4 13 22 31 9n+5 32 5 14 23 9n+6 24 33 6 15 9n+7 16 25 34 7 9n+8 8 17 26 35

Now I am going to duplicate the 9n +1 and 9n+7 plane. The 9n+2 and 9n+8 plane are coloured black (as well as the 4n+2 column). The 9n+5 is coloured yellow.
 4n 4n+1 4n+2 4n+3 9n 36 9 18 27 9n+1 28 1 10 19 9n+1 28 1 10 19 9n+2 20 29 2 11 9n+3 12 21 30 3 9n+4 4 13 22 31 9n+5 32 5 14 23 9n+6 24 33 6 15 9n+7 16 25 34 7 9n+7 16 25 34 7 9n+8 8 17 26 35

If we omit the black planes at 9n+2 and 9n+8 we have two horizontal black planes as in the original diagram (in the proof I talk about merging planes but I think it makes more sense to simply discard them.) The grid contains some repetitions and some numbers in the number chain are missing (but we know they aren't twin primes).

 9n 36 9 18 27 9n+1 28 1 10 19 9n+1 28 1 10 19 9n+3 12 21 30 3 9n+4 4 13 22 31 9n+5 32 5 14 23 9n+6 24 33 6 15 9n+7 16 25 34 7 9n+7 16 25 34 7

Next we need to extend this up to the 25n plane. The first few slices look like this (before they are sorted by their residue mod 25):

 36 9 18 27 28 1 10 19 28 1 10 19 12 21 30 3 4 13 22 31 32 5 14 23 24 33 6 15 16 25 34 7 16 25 34 7

 72 45 54 63 64 37 46 55 64 37 46 55 48 57 66 39 40 49 58 67 68 41 50 59 60 69 42 51 52 61 70 43 52 61 70 43

 108 81 90 99 100 73 82 91 100 73 82 91 84 93 102 75 76 85 94 103 104 77 86 95 96 105 78 87 88 97 106 79 88 97 106 79

To make it easier to see what the next stage looks like, I'm going to leave out the black planes and the red plane (in which there are no primes other than 3, which is an exception - it isn't a twin because it is only on one red plane. )

 4n+1 4n+3 9n+1 1 19 9n+1 1 19 9n+4 13 31 9n+4 13 31 9n+5 5 23 9n+7 25 7 9n+7 25 7

Here, the numbers in the green and yellow planes up to 900 have been rearranged by their residue mod 25 (picture this as 25 slices of a cuboid):

25n+2, 25n+12, 25n+17 and 25n+22 are black planes as they can't contain the higher of two twin primes. 25n+5 is red, 25n+7 is yellow.

Next, we are going to substitute:

25n+3 for 25n+2
25n+13 for 25n+12
25n+18 for 25n+17
25n+ 23 for 25n+22

I've highlighted 5 - this is the only number on this grid that won't appear on any more red or yellow planes. There are two instances of 7 (one of which is highlighted) - these will both be on the 49+7 red plane in the next dimension and then no other red planes.

The first prime that is a non-twin is 11 - this has already been removed from the pattern when we coloured the 9n+2 plane black - we chose to repeat the 9n+1 plane, so you could see the second instance of 19 as a replacement for 11.

Every number that is only in one red plane when this process is reiterated in infinite dimensions will also be on only one yellow plane, so we can treat the yellow plane as being the same as a green plane.*

Given this, the intersection of green, black and red planes in the grid above is the same topological pattern as we would find if we were looking only for primes, but we have multiple repetitions of individual numbers within the pattern.

Also, I talk about rearranging the numbers according to modulo residue above - it would maybe be better to visualise this as a hypercuboid that from the start contains duplications of some planes that aren't either pn or pn+2  and doesn't include any pn+2 planes other than the (p^2)n+p+2 planes.

Hope that all makes sense?

In theory we need to make these plane substitutions in every dimension - I do have one or two thoughts on why that might be problematic, I'll come back to talk about that soon.

*See the algebra in part 7 of the original proof.

## Sunday, 15 July 2012

### Twin Prime Proof Appendix

Here’s a bit more detail on how the first hypercuboid was constructed – this is the simple version before we added the complication of residues of squares. This is a version that is looking for pn and pn+2 numbers (eg twin primes) starting from the point where we have narrowed the possible numbers down to the 2n+1 planes and the 3n+1 planes:

 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 103 109 115 121 127 133 139 145 151 157 163 169 175 181 187 193 199 205

Numbers coloured grey are either 5N or 5N +2.
Numbers coloured blue are either 7N or 7N+2.

We turn this into a box by adding the following five slices starting from each of the five columns:

 1 31 61 91 121 151 181 211 241 271 301 331 361 391 421 451 481 511 541 571 601 631 661 691 721 751 781 811 841 871 901 931 961 991 1021 1051 1081 1111 1141 1171 1201 1231 1261 1291 1321 1351 1381 1411 1441 1471 1501 1531 1561 1591 1621 1651 1681 1711 1741 1771 1801 1831 1861 1891 1921 1951 1981 2011 2041 2071 2101 2131 2161 2191 2221 2251 2281

 7 37 67 97 127 157 187 217 247 277 307 337 367 397 427 457 487 517 547 577 607 637 667 697 727 757 787 817 847 877 907 937 967 997 1027 1057 1087 1117 1147 1177 1207 1237 1267 1297 1327 1357 1387 1417 1447 1477 1507 1537 1567 1597 1627 1657 1687 1717 1747 1777 1807 1837 1867 1897 1927 1957 1987 2017 2047 2077 2107 2137 2167 2197 2227 2257 2287

 13 43 73 103 133 163 193 223 253 283 313 343 373 403 433 463 493 523 553 583 613 643 673 703 733 763 793 823 853 883 913 943 973 1003 1033 1063 1093 1123 1153 1183 1213 1243 1273 1303 1333 1363 1393 1423 1453 1483 1513 1543 1573 1603 1633 1663 1693 1723 1753 1783 1813 1843 1873 1903 1933 1963 1993 2023 2053 2083 2113 2143 2173 2203 2233 2263 2293

 19 49 79 109 139 169 199 229 259 289 319 349 379 409 439 469 499 529 559 589 619 649 679 709 739 769 799 829 859 889 919 949 979 1009 1039 1069 1099 1129 1159 1189 1219 1249 1279 1309 1339 1369 1399 1429 1459 1489 1519 1549 1579 1609 1639 1669 1699 1729 1759 1789 1819 1849 1879 1909 1939 1969 1999 2029 2059 2089 2119 2149 2179 2209 2239 2269 2299

 25 55 85 115 145 175 205 235 265 295 325 355 385 415 445 475 505 535 565 595 625 655 685 715 745 775 805 835 865 895 925 955 985 1015 1045 1075 1105 1135 1165 1195 1225 1255 1285 1315 1345 1375 1405 1435 1465 1495 1525 1555 1585 1615 1645 1675 1705 1735 1765 1795 1825 1855 1885 1915 1945 1975 2005 2035 2065 2095 2125 2155 2185 2215 2245 2275 2305

And as before, note that we can rearrange these to make the planes clearer, for instance:

 5n+1 5n+2 5n+3 5n+4 5n+5 7n+1 1 127 43 169 85 7n+2 121 37 163 79 205 7n+3 31 157 73 199 115 7n+4 151 67 193 109 25 7n+5 61 187 103 19 145 7n+6 181 97 13 139 55 7n+7 91 7 133 49 175

 7n+1 7n+2 7n+3 7n+4 7n+5 7n+6 7n+7 11n+1 1 331 661 991 1321 1651 1981 11n+2 211 541 871 1201 1531 1861 2191 11n+3 421 751 1081 1411 1741 2071 91 11n+4 631 961 1291 1621 1951 2281 301 11n+5 841 1171 1501 1831 2161 181 511 11n+6 1051 1381 1711 2041 61 391 721 11n+7 1261 1591 1921 2251 271 601 931 11n+8 1471 1701 2131 151 481 811 1141 11n+9 1681 2011 31 361 691 1021 1351 11n+10 1891 2211 241 571 901 1231 1561 11n+11 2101 121 451 781 1111 1441 1771

 7n+1 7n+2 7n+3 7n+4 7n+5 7n+6 7n+7 11n+1 463 793 1123 1453 1783 2113 133 11n+2 673 1003 1333 1663 1993 13 343 11n+3 883 1213 1543 1873 2203 223 553 11n+4 1093 1423 1753 2083 103 433 763 11n+5 1303 1633 1963 2293 313 643 973 11n+6 1513 1843 2173 193 523 853 1183 11n+7 1723 2053 73 403 733 1063 1393 11n+8 1933 2263 283 613 943 1273 1603 11n+9 2143 163 493 823 1153 1483 1813 11n+10 43 373 703 1033 1363 1693 2023 11n+11 253 583 913 1243 1573 1903 2233

For the proof above, these diagrams would need to be extended to 25n x 49n grids and 49n x 121n grids, but it is easier just to imagine those…

Appendix B

Just a quick thought on modulo residues:

I find it easiest to think of modulo residues this way – any prime number p has a modulo residue of p for every other prime. For instance, 19 is defined by the infinite set of pn + 19 residues. However, for numbers below 19, you need to convert this into numbers in the appropriate modulo range, so this is equivalent to 2n+1, 3n+1, 5n+4, 7n+5, 11n+8, 13n+6, 17n+2, 19n (or 19n+19) and every pn+19 thereafter.

Appendix C

Some people might not like the "merging" stage of the attempted proof. (it's certainly a bit dodgy as things stand!) An alternative method would be to simply remove the pn+2 planes from the grid at the same time as repeating other green planes. This would leave us with an incomplete number chain, with repetitions. It would still be topologically equivalent to the prime number hypercuboid. And when it comes to the p^2n+p and p^2n+p+2 planes, we could simply ignore one of them since both will contain the same numbers (>3) in locations where they are not intersected by black planes.