## Other

drummers-lowrise
 Advanced search

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

 Post to thread Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120154 - Posted: 27 Aug 2018 | 1:16:44 UTC

Here's a head-scratcher.

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,700
RAC: 24,050

Message 120170 - Posted: 27 Aug 2018 | 17:53:16 UTC - in response to Message 120154.

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120187 - Posted: 28 Aug 2018 | 6:53:25 UTC - in response to Message 120170.
Last modified: 28 Aug 2018 | 6:54:37 UTC

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120391 - Posted: 9 Sep 2018 | 6:57:38 UTC

Waring's conjecture is proven, about 2 hours ago.

Full details to follow after the proof is peer-reviewed 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 hand-written 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 peer-reviewed journal. I guess some degrees are over-rated.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120422 - Posted: 11 Sep 2018 | 0:45:12 UTC

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120704 - Posted: 24 Sep 2018 | 8:14:27 UTC - in response to Message 120422.

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120926 - Posted: 5 Oct 2018 | 17:04:44 UTC

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 16-18).
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 CM-1 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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120933 - Posted: 6 Oct 2018 | 6:27:39 UTC

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.

dukebg
Volunteer tester

Joined: 21 Nov 17
Posts: 240
ID: 950482
Credit: 23,670,125
RAC: 0

Message 120935 - Posted: 6 Oct 2018 | 7:38:55 UTC

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!

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120938 - Posted: 6 Oct 2018 | 10:22:06 UTC - in response to Message 120935.
Last modified: 6 Oct 2018 | 10:28:40 UTC

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 Hilbert-Waring 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 high-ranking member of the US State Department,
the one who released the 83-page 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 dead-man's switch which dumps it to the dark web.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120947 - Posted: 6 Oct 2018 | 18:30:53 UTC - in response to Message 120938.
Last modified: 6 Oct 2018 | 18:32:18 UTC

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 grade-school stuff."
Yes, well there is one particularly simple polynomial in 2 variables that has a name.
It's called an elliptic curve. (wikipedia)

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120959 - Posted: 7 Oct 2018 | 14:56:42 UTC - in response to Message 120938.
Last modified: 7 Oct 2018 | 14:57:08 UTC

If you want a good thriller, it has to be plausible and interesting.

On the other hand was Linnik any relation to a high-ranking member of the US State Department,
the one who released the 83-page 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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 120960 - Posted: 7 Oct 2018 | 17:00:05 UTC
Last modified: 7 Oct 2018 | 17:01:49 UTC

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 121825 - Posted: 3 Nov 2018 | 5:50:04 UTC
Last modified: 3 Nov 2018 | 5:55:34 UTC

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.

recoil44

Joined: 20 Dec 15
Posts: 167
ID: 433037
Credit: 411,347,492
RAC: 0

Message 121830 - Posted: 3 Nov 2018 | 13:19:59 UTC - in response to Message 121825.

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 123256 - Posted: 10 Dec 2018 | 8:56:43 UTC - in response to Message 121830.

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 single-spaced typed lines of notes including a lot of dead-end 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 group-think.
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 anti-inflamatory 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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 123298 - Posted: 10 Dec 2018 | 23:58:56 UTC

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 128611 - Posted: 8 Apr 2019 | 18:05:50 UTC

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 ooh-ahh 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 write-up a go now.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 128757 - Posted: 14 Apr 2019 | 16:58:20 UTC

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 128762 - Posted: 15 Apr 2019 | 3:45:43 UTC

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

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 129025 - Posted: 27 Apr 2019 | 6:26:04 UTC
Last modified: 27 Apr 2019 | 6:28:19 UTC

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

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 short-circuited.

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 129060 - Posted: 29 Apr 2019 | 6:12:37 UTC

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 129094 - Posted: 1 May 2019 | 6:27:10 UTC
Last modified: 1 May 2019 | 7:17:35 UTC

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 129198 - Posted: 7 May 2019 | 2:51:50 UTC
Last modified: 7 May 2019 | 2:52:13 UTC

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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 130460 - Posted: 17 Jun 2019 | 12:10:49 UTC

**bbzz* ff ** radio static* something weird is going on here, my program is very slowly converging to the sequence of Poly-Bernoulli 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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 130679 - Posted: 26 Jun 2019 | 17:05:19 UTC

... 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 re-use 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 time-wise and storage-wise 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 memory-wise 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.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 132594 - Posted: 6 Sep 2019 | 12:15:00 UTC

It seems odd to be dispassionate now about saying that I might have a proof of the conjecture, "this time" a proof by contradiction. It was a long and hard journey, and along the way I learned to distrust my gut feeling, after several exciting interludes that amounted to very little progress.

The last time, on the first anniversary of starting to work on the problem, I pulled an all-nighter which I felt went somewhere, that I was at the end of the tunnel. But I held back from saying anything about it, especially here, until I confirmed that it worked. As usual, reflecting on it the next day uncovered an impasse. The only reliable conclusion that I could reach was that logical sensibility was shutting down with prolonged periods of avoided sleep.

But it was refreshing to have another tool on the board. Actually, I was using the new visualization, the product of that night's toil, when I came up with this proof. When I placed a new fact on the diagram where the formula told me to put it, the label on the adjacent fact was begging for a contradiction. That could lead to only one conclusion. So I went for it and did the math.

Ya! It's beautiful. Now I'll give it a couple of days to see if it stands up to more scrutiny.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 132737 - Posted: 10 Sep 2019 | 6:47:02 UTC
Last modified: 10 Sep 2019 | 6:48:55 UTC

Oh oh. I found that I flipped a sign along the way, which means the proof is garbage.
It's time to quit when it stops being fun, and it's juuuust about there.

As sometimes happens with these kinds of explorations, something interesting pops out along the way. I now have a C program that slowly enumerates polybernoulli numbers with k=-2, by partitioning these numbers in some way. The set of numbers adding up to each PolyBernoulli number is symmetric, and OEIS doesn't deliver a clue of what they are, so it will be an interesting challenge to figure out what describes them.

Briefly, I produce a set of keys of various lengths by concatenating the results of a sequence of calculations to produce each key (calculations related to Waring's Problem). Then I sum the parts of the keys together and drop the keys into bins labelled with the sums, while tracking the number of unique keys that appears in each bin. That's where the surprises start.

Surprise #1. For N parts each ranging from 1 to X, there are only N+X-1 distinct sums. For unrelated parts, I expected N*X-N+1 distinct sums. So the parts have some kind of internal parity that binds them tightly to the sequence, even though the parts seem to appear random individually.

Surprise #2. Sorting the bins according to the bin's label, the contents of the bins are symmetric, in the way that binomial coefficients are symmetic. Actually not so surprising, because the middle sums have more degrees of freedom, more ways of achieving the sum for that bin.

Surprise #3. Adding together the contents of the N+X-1 bins produces the Nth PolyBernoulli number with k=-log(X). On reflection, this probably has something to do with the requirement for the uniqueness of the keys; the prior work points to that.

So the only really surprising fact is #1.

composite
Volunteer tester

Joined: 16 Feb 10
Posts: 820
ID: 55391
Credit: 730,003,725
RAC: 386,677

Message 143113 - Posted: 6 Sep 2020 | 22:47:47 UTC
Last modified: 6 Sep 2020 | 22:58:05 UTC

Waking up from a long sleep, I decided to check my understanding of these surprises with a sequence of keys that I understand better: a full keyspace of X^N keys.

With X=100 and N=3, produce the set of all 1'000'000 unique 6-digit (base 10) keys.
Treat these keys as 3 concatenated 2-digit values corresponding to the "results of a sequence of calculations" referred to previously. Unlike the sequence generated from Waring's Problem, these "results" are uniformly distributed (from 0 to 99).

The sum of the 3 values in a key produces a bin number ranging from 0 to 297.
The number of bins is N*X-N+1 as expected for the full keyspace.

Assigning keys to these 298 bins according to bin number, let the count of keys in a bin be called the contents of the bin.

The total contents of all the bins is clearly 1'000'000 because all we've done is partitioned the set of keys into bins according to a rule. Stepping through the bins in order of ascending bin number, we see the contents are 1, 3, 6, 10, 15, 21, ..., 4851, 4950, 5050, 5148, 5244, 5338, ..., 7494, 7498, 7500, 7500, 7498, 7494, ..., 5244, 5148, 5050, 4950, ..., 21, 15, 10, 6, 3, 1. The sequence is symmetric about the maximum value.

The first difference of that sequence shows us what's going on. This is [1], 2, 3, 4, 5, ... , 98, 99, 100, 98, 96, 94, 92, ..., 6, 4, 2, 0, -2, -4, -6, ..., -96, -98, -100, -99, -98, -97, ..., -6, -5, -4, -3, -2, -1. With an initial [1] as an extension for symmetry, the difference sequence is one cycle of a triangle wave with negative slope twice the positive slope.

Now, do this again, but modify the keyspace by throwing away all keys containing a "00" for one or more of the "results". This removes 10'000 + 10'000 + 10'000 - 100 - 100 - 100 + 1 keys from the keyspace, leaving 970'299 keys with "results" from 1 to 99. Now there are 295 bins, having lost bins numbered 0, 1, and 2 from the previous case. The sequence of bin contents is similar: 1, 3, 6, 10, ..., 4753, 4851, 4950, 5047, 5142, ..., 7347, 7350, 7351, 7350, 7357, ..., 5142, 5047, 4950, 4851, 4753, ..., 10, 6, 3, 1, except that the sequence starts at bin 3 and progresses such that the extrema of the difference sequence are 99 and -99 rather than 100 and -100. Again, the sequence is symmetric about the maximum value.

We can throw away a set of keys from the full keyspace according to more complex rules. If we use a keyspace that is a power of 2 rather than a power of 10, and we throw away keys according to rules that generate a keyspace whose size is the PolyBernoulli number with k=-2, then we can get the observed sequence behaviour. Now it's not really so surprising that the sequence is symmetric and the number of distinct sums is so different from what I originally expected.

So what I've discovered is a connection between some recursion formulae I developed for Waring's Problem and Brewbaker's combinatorial interpretation of the Poly-Bernoulli numbers. Since I know the recursion formulae produce a restricted keyspace, I hope to map Brewbaker's combinatorial generator onto the allowed ranges for resides that makes Waring's conjecture true.

{edit} If that leads to the answer, then Waring simply didn't have a chance because he didn't have the tools 250 years ago.

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 3.51, 3.14, 3.57
Generated 13 May 2021 | 22:41:36 UTC