<p>The Fueter–Pólya conjecture states that if <span class="math-container">$\pi$</span> is a polynomial function and a bijection from <span class="math-container">$\mathbb{N}^2$</span> to <span class="math-container">$\mathbb{N}$</span> then <span class="math-container">$\pi$</span> must be the Cantor pairing function (<span class="math-container">$(x,y) \mapsto 1/2(x + y)(x + y + 1) + y$</span>).</p>
<p>The Fueter–Pólya theorem states that if <span class="math-container">$\pi$</span> is of degree 2, then <span class="math-container">$\pi$</span> is the Cantor pairing function.</p>
<p>Now I've always been told that the Fueter–Pólya conjecture was open, but someone claims to have a proof of it here <a href="https://arxiv.org/abs/1809.09871" rel="nofollow noreferrer">https://arxiv.org/abs/1809.09871</a>, the result is even quoted on <a href="https://en.wikipedia.org/wiki/Fueter%E2%80%93P%C3%B3lya_theorem" rel="nofollow noreferrer">wikipedia</a> (yes, I know, it doesn't mean much). Now I wouldn't usually trust a preprint and this one seems a bit sketchy and lacking details at this time, but it seems to me that the core argument makes sense (or can make sense if you fill in the holes left by the author). I would enjoy any enlightenment on this issue.</p>
<p>Edit: I believe the paper to severely lack some details (or it's me) however there are some merits to it I think. Here is how I try to “salvage” the proof, I hope it can highlight why I think the original paper has merits:</p>
<p>Let <span class="math-container">$f$</span> be a polynomial bijection from <span class="math-container">$\mathbb{N}^2$</span> to <span class="math-container">$\mathbb{N}^2$</span> of degree <span class="math-container">$n$</span>.</p>
<p>Fact: since <span class="math-container">$f$</span> is a bijection <span class="math-container">$K(f(x,y))=K(x,y)$</span> for all <span class="math-container">$x,y$</span> (constants are not included).</p>
<p>Fact: <span class="math-container">$K(x)=\log(x)$</span> for almost all <span class="math-container">$x$</span>.</p>
<p>Fact: for <span class="math-container">$n$</span> big enough almost all pairs <span class="math-container">$(x,y)$</span> such that <span class="math-container">$x \$ y$</span> is <span class="math-container">$2n$</span> bit long (where <span class="math-container">$\$$</span> denotes concatenation) you have <span class="math-container">$K(x,y)=K(x)+K(y)$</span>.</p>
<p>Now take <span class="math-container">$w$</span> to be an uncompressible integer such that <span class="math-container">$w=f(x,y)$</span> for some <span class="math-container">$x$</span> and <span class="math-container">$y$</span> and such that <span class="math-container">$K(x,y) = K(x) +K(y)$</span> and such that <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are uncompressible, also take <span class="math-container">$w = f(x,y) \approx (x+y)^n$</span>  (I think you can force it by density of uncompressible integers, and basic results on polynomials (most outputs of a polynomial of degree <span class="math-container">$n$</span> are <span class="math-container">$\approx i^n$</span> where <span class="math-container">$i$</span> is the input).</p>
<p>Then <span class="math-container">$K(w)=n\log(x+y)=K(x)+K(y)$</span>, if on top of what we said we also impose that <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are integers of almost the same size (which may be possible by density once again) then we get <span class="math-container">$K(w)=n\log(2x)=K(x)+K(x) \Rightarrow^{\text{$x$ incompressible}} n\log(x)=2\log(x) \Rightarrow n=2$</span>. By the Fueter–Pólya theorem we conclude that <span class="math-container">$f$</span> is the Cantor pairing function.</p>

CC BY-SA 4.0
2023-07-21T18:51:53.467Z
Please don't use "EDIT".  Instead, revise the question so it is self-contained and reads well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755.
D.W.
CC BY-SA 4.0
2023-07-21T18:53:21.373Z
Asking us to review an entire paper is too much for this site.  Especially when it claims to resolve a long-standing open problem, and has some severe flaws, and then you are trying to sketch some repairs and are also simultaneously asking us to check the correctness of those repairs (and based on only a sketch).  That's beyond the scope of what's reasonable to expect in a single answer on this site.
D.W.
CC BY-SA 4.0
2023-07-22T14:27:43.337Z
@user3508551 Perelman and Alon are both retired, so they are not exactly in need to acquire new funding. Being a Fields medalist is probably enough to get an ArXiV submission reviewed that claims to solve Poincaré's conjecture. This is such an edge case, that it's misleading.
Martin Berger
CC BY-SA 4.0
2023-07-22T14:29:12.013Z
@user3508551 I just looked at Alon's Google Scholar page: for 2023 alone more than half of the entries are formally published, and not just Arxiv. I imagine that some of the 2023 Arxiv papers are preprints and will eventually be formally published.
Martin Berger
CC BY-SA 4.0
2023-07-22T22:46:41.653Z
Hence why I wrote “top”. What you wrote on Noga also doesn’t contradict what I wrote. Again, I know several tenured professors with funding who don’t need to be in the rat race; it’s not universal and you know it. By definition, “top” is an edge case.
user3508551
CC BY-SA 4.0
2023-07-23T14:04:15.167Z
@D.W. If it takes too long for you, or is not interesting enough to you then don't bother. I think the conjecture is interesting and the paper worthy enough of inspection, i'd say it takes 30 min to grasp the whole thing including my revisions.  I've spent hours thinking about random questions asked by people on this website. Now I can't forward the paper to a review comitee and in case the paper is correct I can't forward them my own version. I would be interested in what you think the correct course of action is, and what is the threshold of "research level questions" warranted on S.E.
ULechine
CC BY-SA 4.0
2023-07-24T23:26:44.697Z
I think what DW is saying is not that it is not interesting or doesn't deserve careful reading and discussion, but that this particular Q&A site is not a good place for that. This is after all a Q&A site and asking for reviews or correctness evaluation of such papers is not a good fit. E.g. if reply yes, it is correct, would you be satisfied? or if I answer no, it has mistakes, would that satisfy you? They won't.
Kaveh
CC BY-SA 4.0
2023-07-24T23:28:56.650Z
The right thing here is to wait for it to be peer reviewed. If there is a particular part of the paper that you have specific questions about, e.g. in section X how does he get from A to B, or similar reasonably scoped questions, that can be a suitable question here.
Kaveh
CC BY-SA 4.0
2023-07-25T03:50:52.413Z
If you actually click on the arxiv link and then take a look at the PDF, you will see the following at the bottom of the first page "Preprint submitted to Information Processing Letters September 27, 2018". Perhaps the reviewers were not able to reach a conclusion one way or another, so the author simply put it on arxiv after ~5 years. I do not think he would have put it on arxiv if the reviewers were able to find holes in it, but who knows! Ok
Tayfun Pay
CC BY-SA 4.0
2023-07-25T05:37:08.667Z
@TayfunPay What do you mean by “put it on arxiv after ~5 years”? The arxiv submission is also from September 2018.
Emil Jeřábek
CC BY-SA 4.0
2023-07-25T16:04:59.067Z
@Kaveh what do you mean ? No I won't be satisfied by either answer, but most answers on SE aren't yes/no. I would be interested in knowing why it's yes or no, that's the whole point of my post (??) I think my post is perfectly fine for SE. If you have an idea where I should post instead please tell me, I don't know of another website more suited than S.E.
ULechine
CC BY-SA 4.0
2023-07-25T16:07:50.167Z
@TayfunPay I don't know this journal/conference. However I think it's the complete opposite, if it were correct the paper would have been published (it's quite an old conjecture) and not put on arkiv, especially under this form. That said, it may have been rejected for unreadability reasons, so I hope there are still ideas left to be salvaged.
ULechine
CC BY-SA 4.0
2023-07-25T23:05:03.830Z
why the answer is yes/no would not normally fit an answer on this Q&A, that is the reason such questions are typically closed here as the scope is too large and not specific enough.
Kaveh
<algebraic-complexity>
Is the Fueter-Polya Conjecture proven
ULechine
# Is the Fueter-Polya Conjecture proven

(Asked by: username_0 on 2023-07-20)

The Fueter–Pólya conjecture states that if $\pi$ is a polynomial function and a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ then $\pi$ must be the Cantor pairing function ($(x,y) \mapsto 1/2(x + y)(x + y + 1) + y$).

The Fueter–Pólya theorem states that if $\pi$ is of degree 2, then $\pi$ is the Cantor pairing function.

Now I've always been told that the Fueter–Pólya conjecture was open, but someone claims to have a proof of it here <https://arxiv.org/abs/1809.09871>, the result is even quoted on [wikipedia](https://en.wikipedia.org/wiki/Fueter%E2%80%93P%C3%B3lya_theorem) (yes, I know, it doesn't mean much). Now I wouldn't usually trust a preprint and this one seems a bit sketchy and lacking details at this time, but it seems to me that the core argument makes sense (or can make sense if you fill in the holes left by the author). I would enjoy any enlightenment on this issue.

Edit: I believe the paper to severely lack some details (or it's me) however there are some merits to it I think. Here is how I try to “salvage” the proof, I hope it can highlight why I think the original paper has merits:

Let $f$ be a polynomial bijection from $\mathbb{N}^2$ to $\mathbb{N}^2$ of degree $n$.

Fact: since $f$ is a bijection $K(f(x,y))=K(x,y)$ for all $x,y$ (constants are not included).

Fact: $K(x)=\log(x)$ for almost all $x$.

Fact: for $n$ big enough almost all pairs $(x,y)$ such that $x \$ y$ is $2n$ bit long (where $\$$ denotes concatenation) you have $K(x,y)=K(x)+K(y)$.

Now take $w$ to be an uncompressible integer such that $w=f(x,y)$ for some $x$ and $y$ and such that $K(x,y) = K(x) +K(y)$ and such that $x$ and $y$ are uncompressible, also take $w = f(x,y) \approx (x+y)^n$ (I think you can force it by density of uncompressible integers, and basic results on polynomials (most outputs of a polynomial of degree $n$ are $\approx i^n$ where $i$ is the input).

Then $K(w)=n\log(x+y)=K(x)+K(y)$, if on top of what we said we also impose that $x$ and $y$ are integers of almost the same size (which may be possible by density once again) then we get $K(w)=n\log(2x)=K(x)+K(x) \Rightarrow^{\text{$x$ incompressible}} n\log(x)=2\log(x) \Rightarrow n=2$. By the Fueter–Pólya theorem we conclude that $f$ is the Cantor pairing function.

**Tags:** algebraic-complexity

> **Comments:**
> **username_1**: Please don't use "EDIT".  Instead, revise the question so it is self-contained and reads well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755.  
> **username_1**: Asking us to review an entire paper is too much for this site.  Especially when it claims to resolve a long-standing open problem, and has some severe flaws, and then you are trying to sketch some repairs and are also simultaneously asking us to check the correctness of those repairs (and based on only a sketch).  That's beyond the scope of what's reasonable to expect in a single answer on this site.  
> **username_2**: @username_3 Perelman and Alon are both retired, so they are not exactly in need to acquire new funding. Being a Fields medalist is probably enough to get an ArXiV submission reviewed that claims to solve Poincaré's conjecture. This is such an edge case, that it's misleading.  
> **username_2**: @username_3 I just looked at Alon's Google Scholar page: for 2023 alone more than half of the entries are formally published, and not just Arxiv. I imagine that some of the 2023 Arxiv papers are preprints and will eventually be formally published.  
> **username_3**: Hence why I wrote “top”. What you wrote on Noga also doesn’t contradict what I wrote. Again, I know several tenured professors with funding who don’t need to be in the rat race; it’s not universal and you know it. By definition, “top” is an edge case.  
> **username_0**: @username_1 If it takes too long for you, or is not interesting enough to you then don't bother. I think the conjecture is interesting and the paper worthy enough of inspection, i'd say it takes 30 min to grasp the whole thing including my revisions.  I've spent hours thinking about random questions asked by people on this website. Now I can't forward the paper to a review comitee and in case the paper is correct I can't forward them my own version. I would be interested in what you think the correct course of action is, and what is the threshold of "research level questions" warranted on S.E.  
> **username_4**: I think what DW is saying is not that it is not interesting or doesn't deserve careful reading and discussion, but that this particular Q&A site is not a good place for that. This is after all a Q&A site and asking for reviews or correctness evaluation of such papers is not a good fit. E.g. if reply yes, it is correct, would you be satisfied? or if I answer no, it has mistakes, would that satisfy you? They won't.  
> **username_4**: The right thing here is to wait for it to be peer reviewed. If there is a particular part of the paper that you have specific questions about, e.g. in section X how does he get from A to B, or similar reasonably scoped questions, that can be a suitable question here.  
> **username_5**: If you actually click on the arxiv link and then take a look at the PDF, you will see the following at the bottom of the first page "Preprint submitted to Information Processing Letters September 27, 2018". Perhaps the reviewers were not able to reach a conclusion one way or another, so the author simply put it on arxiv after ~5 years. I do not think he would have put it on arxiv if the reviewers were able to find holes in it, but who knows! Ok  
> **username_6**: @TayfunPay What do you mean by “put it on arxiv after ~5 years”? The arxiv submission is also from September 2018.  
> **username_0**: @username_4 what do you mean ? No I won't be satisfied by either answer, but most answers on SE aren't yes/no. I would be interested in knowing why it's yes or no, that's the whole point of my post (??) I think my post is perfectly fine for SE. If you have an idea where I should post instead please tell me, I don't know of another website more suited than S.E.  
> **username_0**: @TayfunPay I don't know this journal/conference. However I think it's the complete opposite, if it were correct the paper would have been published (it's quite an old conjecture) and not put on arkiv, especially under this form. That said, it may have been rejected for unreadability reasons, so I hope there are still ideas left to be salvaged.  
> **username_4**: why the answer is yes/no would not normally fit an answer on this Q&A, that is the reason such questions are typically closed here as the scope is too large and not specific enough.  

---

## 0 answers

