goldbach

Cappallo-Goldbach Conjecture

Three new recent discoveries.

First,

it turns out that you can generate a complete list of primes in the following fashion.

Using %n% where %p + q = 2n%, let %n = 2% and find any Goldbach partitions %p, q%; if %max(q in bb Q)% is not in set %bb P%, add that %q% to %bb P%. This will generate a set %bb P% such that %bb P% contains every prime up through %2n-3%, in order. Furthermore, the corresponding values of %p% will be small. I haven't determined exactly, but I am confident of %p <= sqrt(2n)% as an upper bound.

Sketch of proof

Let %q% be some prime not yet in %bb P%. The first possible inclusion of %q% in a Goldbach pair will be %3 + q = 2n%, and as soon as %n = (q + 3)/2%, you will have that %q%, and it will be the largest such %q% for that %n%.

There are repeats (corresponding to prime gaps) and even backtracks of the largest %q% (deserving further investigation), but they necessarily consist of primes already in %bb P%.

Second,

the Cappallo-Goldbach Conjecture, refining the domain of %p% and %q% to make a stronger assertion:

%sf"For any even " N > 2,sf" there exist primes " p, q sf" such that "% %p + q = N sf" and " sqrt(N) <= p <= N//2 <= q <= N - sqrt(N).%

If true, this bound is an improvement on the original %2 <= p <= N//2 <= q <= N-2%.

Or, more simply: there will always be a valid %p% such that %p >= sqrt(N)%.

Note also that there need not be a %p < sqrt(N)%; the first such counter-example is found at %N = 98%, yielding %19 + 79% as the smallest of three partitions.

I have not proven why this should be, but confirmed it empirically through %N = 5000%. I find it suggestive that %N - sqrt(N) = sqrt(N)(sqrt(N) - 1)%, which is reminiscent of the binomial expressions which can also be used to identify primes.

For instance, it appears likely (see Lehmer's totient problem) that for any prime %p%, it must be possible to factor %p - 1% into an arbitrary number of terms of the form %(k^n - k^(n-1))%, where %k% is a unique prime and %n >= 1, n in NN%.

This also likely connects to results such as the %i%th row of Pascal's Triangle consisting only of multiples of %i " iff " i% is prime: or equivalently, that %p in bbb P iff {p:" " p | ((p),(i)) :}, 0 < i < p}%.

Third,

the set of all Goldbach numbers have a bijective mapping to the set of all semiprimes.

Goldbach diagonals

The numbers going across the top represent our %n%. Visually, if one drops a vertical line to meet the diagonal, and then travels on a down/left diagonal, any intersections crossed represent Goldbach pairs.

For example, the line dropped from %8% hits the intersection of the horizontal %11% line and the vertical %5% line, meaning that %5 + 11 = 2(8)% is a solution; the same applies to %3 + 13 = 2(8)%. Since every semiprime can be represented as intersections on this sort of diagram, and every Goldbach pair will likewise be generated once, when intersecting a semiprime, the mapping becomes apparent.

Alternatively, consider that any semiprime is the product of two specific primes, and conversely, any two primes form a unique semiprime. Likewise, any Goldbach pair consists of two specific primes, and while their sum may not be unique among Goldbach pairs, that pair will still only be used a single time in the set of all Goldbach pairs, providing our one-to-one map. As addition and multiplication are both commutative, ordering is irrelevant; it suffices to either always lead by the smaller/larger of the two operands, or allow both orderings when taking the sum or product.

Analysis

(Under construction.)

For starters, it is known that there are infinite primes, thus infinite semiprimes, which in turn provides another proof of infinite Goldbach pairs. I also reason that since any given even number has a finite number of Goldbach pairs, there must be an infinite number of Goldbach sums—that is, even numbers with at least one Goldbach pair. If there were only a finite number of these sums, each with a finite number of Goldbach pairs, we would lose our bijection. Unfortunately, this is necessary but not sufficient to prove Goldbach's Conjecture, as the infinitude of sums says nothing about their frequency within %NN%.

There should be other low-hanging fruit here. For example, since it is ...

It is interesting that while the product of two primes is a unique integer, the sum of a Goldbach pair is typically not (e.g. %3+13=5+11=16%). However, because of our one-to-one mapping, we know that the number of semiprimes must equal the number of Goldbach sums.

Let's look at bounding %p% and %q%. If we choose some %C% such that %p <= q <= C%, we yield %(pi^2(C)+pi(C))/2% semiprimes / Goldbach pairs.

(Ignoring %2%s for the moment...)

Let %C=7%.

  • %3 * 3 = 9%
  • %3 * 5 = 15%
  • %3 * 7 = 21%
  • %5 * 5 = 25%
  • %5 * 7 = 35%
  • %7 * 7 = 49%
  • %3 + 3 = 2(3) = 6%
  • %3 + 5 = 2(4) = 8%
  • %3 + 7 = 2(5) = 10%
  • %5 + 5 = 2(5) = 10%
  • %5 + 7 = 2(6) = 12%
  • %7 + 7 = 2(7) = 14%

Let %C = 17%. We obtain the following semiprimes:

  • %3 * 3 = 9%
  • %3 * 5 = 15%
  • %3 * 7 = 21%
  • %3 * 11 = 33%
  • %3 * 13 = 39%
  • %3 * 17 = 51%
  • %5 * 5 = 25%
  • %5 * 7 = 35%
  • %5 * 11 = 55%
  • %5 * 13 = 65%
  • %5 * 17 = 85%
  • %7 * 7 = 49%
  • %7 * 11 = 77%
  • %7 * 13 = 91%
  • %7 * 17 = 119%
  • %11 * 11 = 121%
  • %11 * 13 = 143%
  • %11 * 17 = 187%
  • %13 * 13 = 169%
  • %13 * 17 = 221%
  • %17 * 17 = 289%

All semiprimes will be unique, and they will be bounded above by %C^2% and below by %3^2%.

We obtain the following Goldbach partitions:

  • %3 + 3 = 2(3) = 6%
  • %3 + 5 = 2(4) = 8%
  • %3 + 7 = 2(5) = 10%
  • %3 + 11 = 2(7) = 14%
  • %3 + 13 = 2(8) = 16%
  • %3 + 17 = 2(10) = 20%
  • %5 + 5 = 2(5) = 10%
  • %5 + 7 = 2(6) = 12%
  • %5 + 11 = 2(8) = 16%
  • %5 + 13 = 2(9) = 18%
  • %5 + 17 = 2(11) = 22%
  • %7 + 7 = 2(7) = 14%
  • %7 + 11 = 2(9) = 18%
  • %7 + 13 = 2(10) = 20%
  • %7 + 17 = 2(12) = 24%
  • %11 + 11 = 2(11) = 22%
  • %11 + 13 = 2(12) = 24%
  • %11 + 17 = 2(14) = 28%
  • %13 + 13 = 2(13) = 26%
  • %13 + 17 = 2(15) = 30%
  • %17 + 17 = 2(17) = 34%

All Goldbach pairs will be unique, and their sums bounded above by %2C% and below by %2*3%.

I have been working through this without knowing where I was going, but now that I re-read this last part, it strikes me that the Goldbach bounds are the derivatives of the semiprime bounds with respect to the bound.

Reflection

I believe the first observation is essentially trivial number manipulation and contains no new useful truth. I have not yet formed an opinion about the utility of the second.

Goldbach as bitfield

I've been trying to visualize the problem in many different ways, tables and graphs and geometry and anything else that seems plausible. Here's one I nailed down this morning that's concise and readily graspable for any coder.


First, ignore the %2%. It just gets in the way.

And then we get going. Starting with %3%, we'll build up a list of primes and I'll show how you can easily check for Goldbach numbers while you do. As you build a string of bits, on each new number, you reverse the bits you have so far and slide it over one.

Much easier understood with a demonstration, starting with %n=6 => n/2=3% and incrementing %n=n+2%, as it must be even.

n=6   3
prm?  1
rev   1

n=8   3 5
prm?  1 1
rev   1 1

n=10  3 5 7
prm?  1 1 1
rev   1 1 1

n=12  3 5 7 9
prm?  1 1 1 0
rev   0 1 1 1

n=14  3 5 7 9 11
prm?  1 1 1 0 1
rev   1 0 1 1 1

n=16  3 5 7 9 11 13
prm?  1 1 1 0  1  1
rev   1 1 0 1  1  1

n=18  3 5 7 9 11 13 15
prm?  1 1 1 0  1  1  0
rev   0 1 1 0  1  1  1

n=20  3 5 7 9 11 13 15 17
prm?  1 1 1 0  1  1  0  1
rev   1 0 1 1  0  1  1  1

All we're doing with rev is reversing the order of the "prime?" bits. If you watch from one to the next, you can see that this is actually resulting in a kind of ongoing shift each time. Observe:

prm?   1  1  1  0  1  1  0  1  1  0  1  0  0  1
n      3  5  7  9 11 13 15 17 19 21 23 25 27 29
6      1
8      1  1
10     1  1  1
12     0  1  1  1
14     1  0  1  1  1
16     1  1  0  1  1  1
18     0  1  1  0  1  1  1
20     1  0  1  1  0  1  1  1
22     1  1  0  1  1  0  1  1  1
24     0  1  1  0  1  1  0  1  1  1
26     1  0  1  1  0  1  1  0  1  1  1
28     0  1  0  1  1  0  1  1  0  1  1  1
30     0  0  1  0  1  1  0  1  1  0  1  1  1
32     1  0  0  1  0  1  1  0  1  1  0  1  1  1

Notice all we are doing, for each new line, is taking %prm?(n)%, sticking it at the beginning of the new line, and shoving over all the rest. Same as above, but easier to see here. Note also the prime bits read down vertically in the regular order.

So?

The thing is, you can check for any and all Goldbach numbers by simply bitwise ANDing two corresponding strings together. (This may actually be an efficient way to code this, should such a need arise.) Take %n=28%:

       3  5  7  9 11 13 15 17 19 21 23 25
prm?   1  1  1  0  1  1  0  1  1  0  1  0
rev    0  1  0  1  1  0  1  1  0  1  1  1
-----------------------------------------
  &    0  1  0  0  1  0  0  1  0  0  0  1

The resulting bits identify which numbers are "Goldbach numbers," primes which will sum to %n%. In this case we get two pairs:

%5 + 23 = 28%
%11 + 17 = 28%

This process will give you all valid Goldbach numbers for a given %n%.

  prm? 1  1  1  0  1  1  0  1  1  0  1  0  0  1
n      3  5  7  9 11 13 15 17 19 21 23 25 27 29
6     (1)                                            3+3=6
8     (1  1)                                         3+5=8
10    (1 (1) 1)                                      3+7=10   5+5=10
12     0 (1  1) 1                                    5+7=12
14    (1  0 (1) 1  1)                                3+11=14  7+7=14
16    (1 (1  0  1  1) 1)                             3+13=16  5+11=16
18     0 (1 (1  0  1) 1) 1                           5+13=18  7+11=18

...and so on. I added the parentheses to emphasize the pairs, but it's just matching up by working from the outsides to the center. It did make me notice something I should have seen before, which is that if you don't want to bother with all the reversing and stuff, you accomplish the same thing by taking the prime bit string, counting in from both sides, and watching for matches that are both 1. Same exact thing.


The astute observer may point out that I'm not actually doing anything in this write-up, which is true. Especially viewed this most recent way, all we're doing is literally taking the Goldbach Conjecture by its definition, and looking manually for pairs of primes that add up. If there is something to be gained from this approach, I suspect it lies in study of the "sliding" nature of the reversal version, and seeing how it conspires not to leave holes.

This is almost certainly biased on my hunch that Goldbach's undoing lies in a thorough examination of the mechanism driving its avoidance of symmetry; to violate Goldbach, there would have to be an instance of a certain symmetry, which would in turn be representative of a periodic pattern to a degree verboten to primes.

But hey, that's just me.

Goldbach modding

I discovered a new (to me) way of approaching the Goldbach problem; this is a brief overview.

Scratch page [ HTML | PDF ]

Trying to prove there are always primes %p, q% such that %p+q = N% for any even %N > 2%, where %p <= q%.

N.B. Largely ignoring 2 as a prime as it seems irrelevant here. There are a couple of 2-related edge cases (%N=4=2+2%) which I'm setting aside as trivial for now. Also disregarding meta-knowledge that this solution is too simple.


Update 2015.09.04

For generating %R%, %\sqrt(N)% insufficient except for small %N%. %N/2% works as an upper bound, but conceivably something as low as %N/3%.

Other thoughts: setting %N//2% to a primorial may be useful for generating primes. For example, letting %N//2 = #(3) = 2 \cdot 3 \cdot 5 = 30% and running through the below with %R = {3,5,7}% gives you %S = {7, 13, 17, 19, 23, 29}% yielding %Q = {53, 47, 43, 41, 37, 31}%, all the primes in %[N//2, N]% save %59%.


I assert that you can obtain all values of %p% for any %N% by the following:

%"Let " S = "set of all primes" <= N//2.%
%"Let "R = "set of all primes" <= sqrt(N).%

For each prime %r∈R%, create a set constrained within the bounds %[3, N//2 − 1]%, starting with the value %N mod r% and incrementing by %r%. Even and non-prime values may be omitted.

e.g. If %N=42%, %r=3%, then %42 -= 0" (mod 3)"%, and generate %{3, 6, 9, 12, 15, 18}%, or simply %{3}.%

Repeat this for every value of %r% in the domain. In the above example, the only other value is %r=5%, yielding %42 -= 2" (mod 5)"%, and consequently %{7, 12, 17}% or just %{7, 17}%. Once complete, remove the generated terms from %S%, your list of all primes in %2 < s < N//2%. We should have:

%S = {3, 5, 7, 11, 13, 17, 19}" \ "{3, 7, 17} = {5, 11, 13, 19}%.

And we have obtained all values for %p%:

%5+37=42%
%11+31=42%
%13+29=42%
%19+23=42%

I further assert that one can use this technique to prove Goldbach's Strong Theorem if it is possible to demonstrate that a) this algorithm is universally sound within its domain, and that b) it will always return at least one value.


Below this line are messy self-notes. Ignore it all for now.

(Except maybe the conclusion.)


For a), it seems to work and I'm taking it on faith for now pending further scrutiny.

For b), I've had several thoughts.

I suspect there may be a basic line of reasoning that is sufficient. As I understand it, the only time an %r% value can be removed is if %r | N%, as happened with %3% in the example. Attempts to remove things straightforwardly appear self-defeating, as in %N = 2*3*5*7 = 210%, which does remove %{3,5,7}% but lets in loads more terms.

Here are some example reference calculations, the terms (up to 50) that would be removed in each case with the given %r% and modulus.

%N mod "__"%

3:

%0=>3% %1=>7, 13, 19, 31, 37, 43% %2=>5, 11, 17, 23, 29, 41, 47%

5:

%0=>5% %1=>11, 31, 41% %2=>7, 17, 37, 47% %3=>3, 13, 23, 43% %4=>19, 29%

7:

%0=>7% %1=>29, 43% %2=>23, 37% %3=>3, 17, 31% %4=>11% %5=>5, 19, 47% %6=>13, 41%

Each value has the same number of primes, a unique and full set! Let's see…

%3+2% gives %7%, %5+2 | 3% gives %4%, %7+3|5% gives %3%
3+2, 5+2, 7+3
5, 7, 10
10, 24, 38, 52, 66, 80, 94, 108, 122
3,5,7,11,17,23,29,31,37,41,47

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
3, 7, 13, 19, 31, 37, 43
7, 13, 19, 37, 43
13, 19, 43

6's, 10's, 14's

This all raises the question… if you take the primes from √N and offset each one however you like, can you hit all the primes up to N/2??

N √N Offense π(N∕2)−1 Defense Gaps
10 3 3 2 3, 5 1
12 3 3 2 3, 5 1
26 5 3, 5 5 3, 5, 7, 11, 13 1, 1, 2, 1
50 7 3, 5, 7 8 3, 5, 7, 11, 13, 1, 1, 2, 1, 17, 19, 23 2, 1, 2

3, 5, 7, 11, 13, 17, 19, 23
3, 7, 13, 19 = 2, 3, 3
5 eats 3, 13
7 eats 7 (or 19)

Surely it's too random. Contradiction proof available?

%3k+A%
%5k+B%
%7k+C%

They can never start on their own spot.

What if we go big?

Let N=1000.

10 attackers, 3 through 31.
94 p-side, 73 q-side.

Or start small:

%N = 10, 12%
%R={3}%
%S={3, 5}%

%N=14, 16, 18, 20%
%S={3, 5, 7}%

%N=22, 24%
%S={3, 5, 7, 11}%

%N=26%
%R={3, 5}%
%S={3, 5, 7, 11, 13}%

%S% terms are generated as the holes made by the %R% sieve. How can you 'invert' the %R% offsets systematically to ensure ideal coverage of those previous holes? (And then prove that's not sufficient to get them all.)

%N=170%
%R={3, 5, 7, 11, 13}%
%S={3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83}%

%N=173% gives %... mod 5 -= 3%

%S={5, 7, 11, 17, 19, 29, 31, 37, 41, 47, 59, 61, 67, 71, 79}%
then 3
%S={7, 19, 31, 37, 61, 67}% then 7
%S={7, 31, 37, 67}% and 11 and 13 do nothing.

%N=122 R={3,5,7,11}%
S={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}
3@61 --> {7, 13, 19, 31, 37, 43, 61}
S={3,5,11,17,23,29,41,47,53,59}
5@59 --> {29, 59}
S={3,5,11,17,23,41,47,53}
7@57 --> {┤
11@53 --> {53}
S={3,5,11,17,23,41,47}


In order not to return some successful value, one would have to craft an %N% such that the union of any applicable sets chosen from the relatively limited domain in %R% cover every single prime up to %N//2%, which I am convinced is an impossibility but haven't yet proven.

If nothing else, there is a strong case to be made where the number of primes in %S% grows strictly faster than the maximum worst-case size of the removal sets (i.e. % |S| ~= (2/3) * (4/5) * (6/7) * ... * |S| % with increasing size of %R%, but seems to lose to growth of % pi (N // 2) % ).