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. )

So we start with this pattern:



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.