Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Duh, what am I missing here?
Author 
Message 

Here's a headscratcher.
Coming back from a wedding party last weekend and seeing the lull in postings on the PG message boards I thought to liven things up by trying to prove the lowest conditional bound of Waring's Problem and post it here. See also the bound for equation 1.1 in this PDF at Penn State U between "provided that" and "if this fails".
It looks easy enough to prove, so why is it still a conjecture?
The first term of the left hand side is the "fractional part" of 3^k / 2^k multiplied by 2^k and second term is the integer part of the same fraction. That's right, the first term is exactly 3^k mod 2^k. But that doesn't matter.
By some obvious conventions let's call the first term R_k (for "remainder") and the second term Q_k (for "quotient"), and S_k for the actual numerical sum.
After a week in the rabbit hole chasing 3^k  R = 2^k Q and getting nowhere fast with a nice recursive expression for Q, I came out of the hole and the sun shone and the birds sang and there it was, sitting in plain sight...
We restate the conjecture as
(1): S_k = R_k + Q_k <= 2^k for k >= 0
According to the references in the links above, relation (1) holds for k <= 417,600,000. So I think we have some material to start an inductive proof. (* sound of rusty gears creaking *)
Just to be sure let's repeat some of that work in my "handy" browser spreadsheet.
k 2^k 3^k Q_k R_k S_k S_k<=2^k
0 1 1 1 0 1 TRUE
1 2 3 1 1 2 TRUE
2 4 9 2 1 3 TRUE
3 8 27 3 3 6 TRUE
4 16 81 5 1 6 TRUE
5 32 243 7 19 23 TRUE
6 64 729 11 25 36 TRUE
7 128 2187 17 11 28 TRUE
Proof:
Assume relation (1) holds for k+1 and we know it holds for k. Let's assess the difference of these sums as k goes to k+1:
(2): S_(k+1)  S_k <= 2^(k+1)  S_k
In general we can express S_k = 2^k  D_k where 0 <= D_k <= 2^k
(3): S_(k+1)  S_k <= 2^(k+1)  2^k + D_k
But 2^(k+1)  2^k = 2^k so
S_(k+1) <= 2^k + D_k
and D_k <= 2^k so
S_(k+1) <= 2^k + D_K <= 2^k + 2^k = 2^(k+1)
Then S_(k+1) <= 2^(k+1)
QED.
Is it really that simple? Please refrain from comments about bricks and marbles.  


This is not likely to be provable by induction.
Proof:
Assume relation (1) holds for k+1 and we know it holds for k. Let's assess the difference of these sums as k goes to k+1:
(2): S_(k+1)  S_k <= 2^(k+1)  S_k
I do not understand. You cannot "assume" the relation holds for k+1 (when we know it holds for k).
You must prove the relation holds for k+1, given that it holds for k. For that you can either (a) assume nothing more and arrive at the desired relation for k+1, or (b) assume the negation of the relation for k+1 and arrive at some kind of contradiction.
/JeppeSN  


Thanks for the refresher and the positive feeding.
I'll see what I can do.  


Waring's conjecture is proven, about 2 hours ago.
Full details to follow after the proof is peerreviewed and published.
I was hoping to use this for a MSc thesis in Computer Science at the local university, but the Department became rather shallow in combinatorics since my former professors retired, and the one I spoke with last week as potential supervisor already has enough grad students for this year. What I showed him wasn't complete, but some of the ideas were correct even though I was barking up the wrong tree at the time. He suggested that I think about choosing another topic, given the high likelihood of not succeeding. I wrote him an email 2 days later saying that I wouldn't be intruding on his time until I solve the problem or I give up and choose something else. Computer Assisted Algebra might be interesting  I started to use one of these packages last weekend to verify my handwritten work and I probably recouped the time to learn it.
I had also spoken with an Associate Dean for a recommendation on a supervisor. He thought this proof would be more appropriate for a thesis in Mathematics than in Computer Science. I'm not keen on doing a math degree, computers are really my area of interest and math courses would burn my brain (but a few whacks on the head might reduce the density sufficiently for higher maths to make sense). He also said, if I have a proof to a named problem, why bother with the degree, just submit it to a peerreviewed journal. I guess some degrees are overrated.  


Withdrawing claim of proof.
Independent review turned up a problem.
Not sure it can be rescued.  


The proof has been fixed. Sending it in for another review today.
 


Another day, another problem. Working on fixing that.
Technically, it's not Waring's conjecture, it's someone else's.
Waring's conjecture suggested that there was any answer at all for every k, which Hilbert proved in 1909.
The problem has been distilled into a set of equations and conditions, and the conjecture is that just one of these equations is needed.
Work on Waring's problem has a very good math pedigree (arxiv.org, pages 1618).
Pillai's work on this problem has been described posthumously as "almost certainly his best piece of work and one of the very best achievements in Indian Mathematics since Ramanujan". (archive.org)
The Associate Dean of Science I spoke with (who's specialty is number theory) is right to be skeptical of any claim of a proof, and he's been correct so far.
The conjecture posits that g(k) = 2^k + floor(3^k/2^k)  2 is the exact answer, rather than merely the only answer we have been able to obtain so far (subject to a condition).
Everyone believes it is true but no one has a proof that the condition is unnecessary.
Furthermore a supercomputer search with a CM1 in 1989 up to k = 471,600,000 by Kubina and Wunderlich failed to find any exceptions (thereby proving that the equation is valid for k up to this much).
From my work on it, I also believe the condition is unnecessary.
This is what I have been working on since August 18, eliminating the condition.
I didn't know what I was walking into when I tackled on this problem on a lark. But I think I'm getting there.
The experience has been like entering A MAZE OF TWISTY LITTLE PASSAGES, ALL DIFFERENT.
But the nature of this maze is that the goal is always visible and always just out of reach.
 


Hey, folks, in case you think I'm writing a short story, maybe I am.
It's been pretty boring up to now, and I can't say much for the title.
Here's the latest installment...
ROFL. I really hit the jackpot this time.
This proof will be perfectly raunchy to a number theorist
because the show is over when the second veil is dropped.
The reviewer said to me, pointing out the mistake in the last iteration,
something like "if you can prove this then you are done immediately".
Looking it over I wondered what brain fart led me to make a statement
that was patently false. And of course my subconscious had been yelling
at me the whole time I as was writing up that drivel,
"HERE!! HEY!!! OVER HERE!!!! IT'S OVER HERE!!! THE PROOF IS OVER HERE, DUMMY!".
The subconscious is never subtle. It communicates through the limbic brain, so I was
really happy when I submitted the proof, which I FELT was correct because, hey,
I eliminated the shenanigans from the first round, and the remaining pieces fit together
so nicely in Lemma 2 and Lemma 3 that I was frankly amazed.
Then a week went by before it was reviewed. Obviously the reviewer wasn't
placing a priority on it after my first failed attempt, saying he might get around
to it on the weekend. And he signed his review more formally, maybe to remind
me that he knows a thing or two more than me and that I was wasting his time.
At least he said that Lemma 2 and Lemma 3 were correct, but they depended
on the result from Lemma 1. Doh! Who knows, he may already have the correct
proof in hand and he is getting pissed off that academic integrity prevents him
from publishing the result himself. What should I do, offer joint authorship, and
at least get my Erdos number reduced to 3 as a consolation prize? He doesn't
have a formal obligation to me. I'm not even registered as a student yet.
But then after a second day and a fitful sleep I got out of bed with the machinery
to make the proof work. Cognizant that I might be wearing down his patience,
I wrote the reviewer a note, asked if this proposed approach could make the
proof work. Encouragingly, he quickly replied yes, as long as the proof is rigourous.
So now it's do or die. He will probably read up to the point where the proof is completely
screaming obvious and tell me that it looks good up to there but that the rest of the proof
is poop because I already provided the answer. I guess I'm just too attached to the small
successes to let the good math go quietly.
 

dukebgVolunteer tester
Send message
Joined: 21 Nov 17 Posts: 232 ID: 950482 Credit: 22,083,013 RAC: 0

Hey, folks, in case you think I'm writing a short story, maybe I am.
It's been pretty boring up to now, and I can't say much for the title.
Here's the latest installment...
Heh, I would say it's actually an interesting short story, not a boring one. Keep the spirits up!  


Hey, folks, in case you think I'm writing a short story, maybe I am.
It's been pretty boring up to now, and I can't say much for the title.
Here's the latest installment...
Heh, I would say it's actually an interesting short story, not a boring one. Keep the spirits up!
You know, the story could easily turn into a conspiracy thriller. Feel free to contribute any facts you can turn up.
For some odd reason, the NSA supported Kubina and Wunderlich's effort with 240 hours of supercomputer time. (semanticscholar.org)
In that paper, these guys, possibly not the first ones to do so, admitted that they "bend the interpretation of history"
in calling the restricted problem at the heart of this investigation, Waring's conjecture.
Was the real purpose of the investigation to probe Waring's hint that this works for polynomials as well?
You know, the Russians have an interest in this too.
Linnik gave an elementary proof of the HilbertWaring Theorem in 1940. (University of Warsaw)
What was the point of that? It was already proven in 1909.
It was wartime, and the Soviets had a secret pact with Nazi Germany to divide up Poland. (wikipedia.org)
The Soviets couldn't afford to spend resources on pure research in wartime. Were they onto something big? (arxiv.org)
And if you Google for Linnick Waring you get NOTHING.
Ya, ok I was sloppy with this one, his name is Linnik and it was a Wikipedia search. (wikipedia.org)
It's not a conspiracy theory unless you make it one.
On the other hand was Linnik any relation to a highranking member of the US State Department,
the one who released the 83page report which distanced them from Hillary Clinton's email practices? (wikipedia.org)
It could be a juicy thriller.
And what if my proof is censored at publication?
Do I get suddenly get a "job" in a certain national security agency?
Alright, so what if I told you that Hardy and Littlewood were out to lunch on this one?
This proof needs a deadman's switch which dumps it to the dark web.  


Was the real purpose of the investigation to probe Waring's hint that this works for polynomials as well?
I hear a chorus of silence asking, "So what's all the fuss about polynomials? That's gradeschool stuff."
Yes, well there is one particularly simple polynomial in 2 variables that has a name.
It's called an elliptic curve. (wikipedia)  


If you want a good thriller, it has to be plausible and interesting. On the other hand was Linnik any relation to a highranking member of the US State Department,
the one who released the 83page report which distanced them from Hillary Clinton's email practices? The similarity in surnames is just a coincidence, and an intergenerational spy ring wouldn't be this obvious.
The Zimmerman Telegram incident (Wikipedia) in the First World War provides a much better story template.
The parallel here would have the Clinton email server hacking as the cover story which hides
the interception of internet traffic and successful decryption of a secure transport mechanism.
The Russians presumably would know if it wasn't them but couldn't be sure they were not a
scapegoat for another hacker like the DPRK. This plotline would follow the theme of this thread.  


Now here's an interesting concept.
Write a fictional story, but embed in it a bona fide firsttime proof of Waring's conjecture.
Is there a precedent for such a thing?  


I've been diddling and dawdling, sitting on the completed proof, and trying to find a shorter one. I may just have to leave this endeavour to someone else, Proving the bound on the conjecture is such a minor result, it's probably not worth trying to find a shorter proof. The real value in any proof is when it introduces new ideas that open up new solution space territory.  


I've been diddling and dawdling, sitting on the completed proof, and trying to find a shorter one. I may just have to leave this endeavour to someone else, Proving the bound on the conjecture is such a minor result, it's probably not worth trying to find a shorter proof. The real value in any proof is when it introduces new ideas that open up new solution space territory.
Rather than not submitting anything, submit what you have and let someone else figure out how to make it shorter.
The real value of any proof is that it changes "we think" to "we know". It adds a stable block on which future knowledge can be built.  


I've been diddling and dawdling, sitting on the completed proof, and trying to find a shorter one. I may just have to leave this endeavour to someone else, Proving the bound on the conjecture is such a minor result, it's probably not worth trying to find a shorter proof. The real value in any proof is when it introduces new ideas that open up new solution space territory.
Rather than not submitting anything, submit what you have and let someone else figure out how to make it shorter.
The real value of any proof is that it changes "we think" to "we know". It adds a stable block on which future knowledge can be built.
It's getting close to the 250 year anniversary of Waring's original problem statement. I'll write up the proof for publication in the new year.
I spent well over 100 hours on this, and have around 760 singlespaced typed lines of notes including a lot of deadend ideas.
I suspect professional mathematicians didn't get this result because they quickly decided they would be more productive working on something else.
The proof exploits 2 ideas I haven't seen used before. You can see the timeline in the previous messages of this thread.
At the beginning I avoided reading previous papers on this problem, to tackle it with a fresh mind and be unaffected by groupthink.
After I had assured my independent approach, I read some of the papers to see what they did.
The first good idea in early September set up a useful framework for the problem.
I was so excited at developing this framework that I was awake and alert for over 40 hours straight.
I managed to relax with a 90 minute massage, but I wasn't sleepy or tired when I forced myself to go to bed a few hours later.
The second idea from early October created the machinery essential to proving a key assertion.
The concept for this machinery emerged while I in the sauna at the public pool I frequented.
This wasn't nearly as exciting as the initial framework, as by now my enthusiasm was tempered by the previous error in the proof I had submitted.
Now here's some added context you haven't seen.
One month before starting this project, I whacked the back of my head pretty hard on the water doing a backflip from a 1 meter springboard.
So I had intermittent headaches for around 3 months, the last two covering the period during which the proof was developed.
During these few months, I speculate there was extra bloodflow augmenting my brain's normal operating level.
Twice I took an antiinflamatory pill to quell the headaches, but I decided to tolerate the headaches after that.
And there may have been some neurological rearrangement from mild shocks to the head, from diving off the 5 metre platform around 80 times since starting in June.
I'm saying there was a process, and maybe it's come to an end (or maybe not).
It's clear from the first post that I wasn't anywhere near a solution when I started.
I haven't felt like doing much work on the proof since the headaches stopped.
I've also recovered from being hit by a car (quite hard) as I was crossing the street in November.
As precaution, I gave my reviewer permission to publish the proof jointly in the event that I somehow become incapacitated (dead) before I can publish it.
It's also become clear to me that although I've long wanted to achieve some result like this, it's not really such an important thing to have done, in the big picture.
I agree with you that the result adds a stable block for future knowledge.
But I double down and assert the framework and machinery in this proof are likely more significant than the result.
Whether there is further use for them in other proofs remains to be seen.  


Ah, "framework" is a bit oversold. It's a construction.  


The proof is getting shorter.
I should retract any claim about machinery. It was a means to an end.
A more fundamental consideration of the problem makes the machinery redundant.
That's the stupid thing about mathematical proofs.
Everyone gets to see the oohahh version without the cruft,
and no clue is revealed about the process that leads to the piÃ¨ce de rÃ©sistance.
I should give the writeup a go now.  


I wrote it up and went to bed, thinking... there it was.
The next day I read it over and decided to tweak a few statements for clarity.
Then I tried the unthinkable. What happens if I invert the logic in the key part?
Oh *&#*! The saga continues. The short proof isn't any good.
Opposite statements work equally well  which means the proof doesn't work at all.
Nice catch. Back to the long version. And maybe that's wrong too.  


I found the booboo in the short proof, so I think I saved it.
Thankfully, it's near the end, so there's not a lot to change.  


I contacted the reviewer and told him "I have something now, I just have to write it up", and "see you soon".
He replied that he would be excited to see it.
A week went by and as I tried to clean up the proof, I was stuck at that same old confounding problem,
because the workaround didn't work. This was after I fixed the booboo.
So for the last couple of days I considered eating crow and sending him another message that I didn't have it.
But then this morning, arguably more in desperation than as obsession, I was turning over the problem
in my head for an hour in bed, without the benefit of a notepad, reiterating the facts as they slipped in
and out of focus, still being nagged by the subconcious about a stupid claim that I know doesn't work.
And TADA!! I saw it. The answer was clear. I did the math in my head. Yup, it worked.
I rushed to the computer and added a couple of columns to my spreadsheet to verify this numerically.
Of course it works. And now I know the reason and I can explain it. The thing that was patently false,
is false for a reason  a reason that I had missed, the reason that makes the proof work. I felt pretty good.
At lunch time I batted the birdie with my buddie in the gym, as we do on Fridays, and I challenged him to try this
wicked general formula with any numbers he chooses, providing they met the criteria I laid out. He's a funny guy.
He used to have a local TV show with a cult following  "Math with Marty". Ya, that's the guy. I've known him since
university days. He's quick with numbers, and he likes to talk about odd theories, but he labours with symbolic
math in his head as much as anyone. There's too much going on. He needs a blackboard to stay organized.
There's one at the gym, but no luck, there's no chalk. So I couldn't explain it to him. He didn't want to listen to me.
He wanted to see it. I'll buy some chalk and bring it next week.
Although he tried it successfully with numerical examples, he couldn't believe that this thing works.
He doesn't want to believe it, but the formula doesn't lie. We sounded like Doc Brown and Marty McFly,
incredulous that no one saw this thing in 3000 years of math history.
No  actually more. Babylonian maths was active from 5th to 3rd millenia BC. Maybe this thing was lost in antiquity.
Realistically though, Babylonian mathematicians probably didn't have it, as they were missing certain tools that
children are now taught in elementary school.
So now the proof is ludicrously short. It has been STARING AT ME FOR NEARLY 6 MONTHS and I didn't see it
for what it was. Kudos to the reviewer, who said to me, that if I could prove this assertion, then I'm done right there.
That was the challenge. Of course my assertion was wrong, but I clung to it because I needed it for a particular
approach to the proof. That approach might still be viable, but it's pointless  the approach has been shortcircuited.
If this proof wasn't such a minor thing, you guys would poop your pants for how simple it is.
(*** Distant echos of Pierre de Fermat's scoffing laughter. ***). Ahhh, just wait for it.
Next up: Goldbach's Conjecture? Yes, I took a stab at this one a few years ago. I had a discussion with a math
professor who looked at me like I'm a kook (I'm starting to see pattern LOL), about an idea he didn't understand.
It's not his field, obviously. I would try to make this idea work, if I ever get a round tuit. Shutting down the GC
distributed computing project would be a nice little contribution to reducing greenhouse gasses.
However, breaking bitcoin would be a much better project for saving the environment.  


Oh, man! Seriously?
I had flipped a sign, so the short proof is messed up.
There has to be a trick in here somewhere, or Pierre wins another round.  


I found the missing link for the short proof. I just have to plug it in.
Threatening checkmate, Pierre!
EDIT: And she's a beauty. This proof will be extremely satisfying. I guarantee it.
EDIT EDIT: Hmmm.
Doubts are creeping up because I haven't been able to plug it in yet.
I might have tricked myself into repeating an old fact in a new way that still doesn't resolve the problem.
Right  just because I see something a new way doesn't mean I can prove it must be that way.  


Direct proof is not going to happen.
The easy case is  easy. And the hard case is  impossible.
I told the reviewer I have abandoned this approach.
So now believe it or not, I'm going to resort to proof by induction, trying to show that the problem is completely covered by just the easy case.
I have some induction formulae and I need to transform the initial problem into these formulae to complete the proof.
I know  this sounds backwards, but I've been working on this thing long enough to already know where all the handles are located.  


**bbzz* ff ** radio static* something weird is going on here, my program is very slowly converging to the sequence of PolyBernoulli numbers B_n^(k) with k=2
Given half a million years, it could converge on the values for n up to 12. Perl is horrible, time to switch to C.  


... and the C program computed in around 2 minutes what the Perl program did in 32 days. That's the difference between using Perl arrays and hashes, versus bit string operations in C, and being able to reuse some intermediate computations in the C version. This includes recompiling the C version with O3, which accounted for a 4.9 times speedup over the unoptimized version, and a modest speedup of 1.3 times by switching from linear search to bisection search (which was penalized by using insertion sort for keys). I think I could do better timewise and storagewise by building a tree.
The benefit of having a Perl implementation for reference is that it was easy to determine the existence of program bugs in the C version, especially in memory addressing. It took a few hours to write the Perl version and over 2 weeks (with sporadic attention) to debug the C version. And I even noted a minor issue in output from the Perl version (index value off by 1, correctible after the fact).
Alas, all it did was confirm a pattern I had previously observed for k up to 250 thousand, extending that range to 30 million in 842 minutes. The arrays gobbled up 10.2 GB of RAM. I could make it more efficient memorywise but there's no point to repeating or extending the computation. It's an interesting result. The hard part is figuring out why I'm seeing this, and if it has any consequence to what I am trying to prove.  

Post to thread
Message boards :
General discussion :
Duh, what am I missing here? 