Mixing
Conjecture about polynomials $f_ninmathbb Q[X_1,dots,X_n]$ defining bijections $mathbb N^ntomathbb N$
$begingroup$
This is inspired by an answer of a question of mine:
Bijective polynomials $finmathbb Q[X_1,dots,X_n]$
There is a polynomial $f_1inmathbb Q[X_1]$ which define a bijection $f_1:mathbb Ntomathbb N$, $f_1(X_1)=X_1$.
There is a polynomial $f_2inmathbb Q[X_1,X_2]$ which define a bijection $f_2:mathbb N^2tomathbb N$,
$displaystyle f_2(X_1,X_2)=frac{(X_1+X_2)(X_1+X_2+1)}{2}+f_1(X_1)$.
And as far as I understand and have tested there is a polynomial $f_3inmathbb Q[X_1,X_2,X_3]$ which define a bijection
$f_3:mathbb N^3tomathbb N$
$displaystyle f_3(X_1,X_2,X_3)=frac{(X_1+X_2+X_3)(X_1+X_2+X_3+1)(X_1+X_2+X_3+2)}{6}+f_2(X_1,X_2)$.
This seems possible to generalize as
$displaystyle f_{n+1}(X_1,dots ,X_{n+1})=f_{n}(X_1,dots ,X_{n})+frac{1}{(n+1)!}prod_{k=1}^{n+1}Big(k-1+sum_{i=1}^{n+1}X_iBig)$.
This is a generalisation of the diagonalization in case of $n=2$ with "triangularization", "tetraederization" or higher. Now the conjecture is
$displaystyle f_n(X_1,dots,X_n)$ define a bijection $mathbb N^ntomathbb N$ for all $n>0$.
Induction seems natural but how to prove that $f_n$ is a bijection implies that $f_{n+1}$ is a bijection?
What I want are proofs, parts of proofs or counter proofs.
algebra-precalculus elementary-number-theory polynomials conjectures
asked Jan 3 at 17:33
LehsLehs
6,99531662
$endgroup$
add a comment |
$begingroup$
This is inspired by an answer of a question of mine:
Bijective polynomials $finmathbb Q[X_1,dots,X_n]$
There is a polynomial $f_1inmathbb Q[X_1]$ which define a bijection $f_1:mathbb Ntomathbb N$, $f_1(X_1)=X_1$.
There is a polynomial $f_2inmathbb Q[X_1,X_2]$ which define a bijection $f_2:mathbb N^2tomathbb N$,
$displaystyle f_2(X_1,X_2)=frac{(X_1+X_2)(X_1+X_2+1)}{2}+f_1(X_1)$.
And as far as I understand and have tested there is a polynomial $f_3inmathbb Q[X_1,X_2,X_3]$ which define a bijection
$f_3:mathbb N^3tomathbb N$
$displaystyle f_3(X_1,X_2,X_3)=frac{(X_1+X_2+X_3)(X_1+X_2+X_3+1)(X_1+X_2+X_3+2)}{6}+f_2(X_1,X_2)$.
This seems possible to generalize as
$displaystyle f_{n+1}(X_1,dots ,X_{n+1})=f_{n}(X_1,dots ,X_{n})+frac{1}{(n+1)!}prod_{k=1}^{n+1}Big(k-1+sum_{i=1}^{n+1}X_iBig)$.
This is a generalisation of the diagonalization in case of $n=2$ with "triangularization", "tetraederization" or higher. Now the conjecture is
$displaystyle f_n(X_1,dots,X_n)$ define a bijection $mathbb N^ntomathbb N$ for all $n>0$.
Induction seems natural but how to prove that $f_n$ is a bijection implies that $f_{n+1}$ is a bijection?
What I want are proofs, parts of proofs or counter proofs.
algebra-precalculus elementary-number-theory polynomials conjectures
asked Jan 3 at 17:33
LehsLehs
6,99531662
$endgroup$
add a comment |
$begingroup$
This is inspired by an answer of a question of mine:
Bijective polynomials $finmathbb Q[X_1,dots,X_n]$
There is a polynomial $f_1inmathbb Q[X_1]$ which define a bijection $f_1:mathbb Ntomathbb N$, $f_1(X_1)=X_1$.
There is a polynomial $f_2inmathbb Q[X_1,X_2]$ which define a bijection $f_2:mathbb N^2tomathbb N$,
$displaystyle f_2(X_1,X_2)=frac{(X_1+X_2)(X_1+X_2+1)}{2}+f_1(X_1)$.
And as far as I understand and have tested there is a polynomial $f_3inmathbb Q[X_1,X_2,X_3]$ which define a bijection
$f_3:mathbb N^3tomathbb N$
$displaystyle f_3(X_1,X_2,X_3)=frac{(X_1+X_2+X_3)(X_1+X_2+X_3+1)(X_1+X_2+X_3+2)}{6}+f_2(X_1,X_2)$.
This seems possible to generalize as
$displaystyle f_{n+1}(X_1,dots ,X_{n+1})=f_{n}(X_1,dots ,X_{n})+frac{1}{(n+1)!}prod_{k=1}^{n+1}Big(k-1+sum_{i=1}^{n+1}X_iBig)$.
This is a generalisation of the diagonalization in case of $n=2$ with "triangularization", "tetraederization" or higher. Now the conjecture is
$displaystyle f_n(X_1,dots,X_n)$ define a bijection $mathbb N^ntomathbb N$ for all $n>0$.
Induction seems natural but how to prove that $f_n$ is a bijection implies that $f_{n+1}$ is a bijection?
What I want are proofs, parts of proofs or counter proofs.
algebra-precalculus elementary-number-theory polynomials conjectures
asked Jan 3 at 17:33
LehsLehs
6,99531662
$endgroup$
This is inspired by an answer of a question of mine:
Bijective polynomials $finmathbb Q[X_1,dots,X_n]$
There is a polynomial $f_1inmathbb Q[X_1]$ which define a bijection $f_1:mathbb Ntomathbb N$, $f_1(X_1)=X_1$.
There is a polynomial $f_2inmathbb Q[X_1,X_2]$ which define a bijection $f_2:mathbb N^2tomathbb N$,
$displaystyle f_2(X_1,X_2)=frac{(X_1+X_2)(X_1+X_2+1)}{2}+f_1(X_1)$.
And as far as I understand and have tested there is a polynomial $f_3inmathbb Q[X_1,X_2,X_3]$ which define a bijection
$f_3:mathbb N^3tomathbb N$
$displaystyle f_3(X_1,X_2,X_3)=frac{(X_1+X_2+X_3)(X_1+X_2+X_3+1)(X_1+X_2+X_3+2)}{6}+f_2(X_1,X_2)$.
This seems possible to generalize as
$displaystyle f_{n+1}(X_1,dots ,X_{n+1})=f_{n}(X_1,dots ,X_{n})+frac{1}{(n+1)!}prod_{k=1}^{n+1}Big(k-1+sum_{i=1}^{n+1}X_iBig)$.
This is a generalisation of the diagonalization in case of $n=2$ with "triangularization", "tetraederization" or higher. Now the conjecture is
$displaystyle f_n(X_1,dots,X_n)$ define a bijection $mathbb N^ntomathbb N$ for all $n>0$.
Induction seems natural but how to prove that $f_n$ is a bijection implies that $f_{n+1}$ is a bijection?
What I want are proofs, parts of proofs or counter proofs.
algebra-precalculus elementary-number-theory polynomials conjectures
algebra-precalculus elementary-number-theory polynomials conjectures
asked Jan 3 at 17:33
LehsLehs
6,99531662
asked Jan 3 at 17:33
LehsLehs
6,99531662
edited Jan 4 at 13:16
Lehs
asked Jan 3 at 17:33
LehsLehs
6,99531662
asked Jan 3 at 17:33
LehsLehs
6,99531662
asked Jan 3 at 17:33
LehsLehs
6,99531662
6,99531662
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The diagonalization argument can indeed be generalized. Roughly, one can see all elements of $mathbb{N}$ appear in order by going through all hyperplanes $X_1+ldots+X_n = s$.
Now for the proof. Let $s=X_1+...+X_n$. Then your function $f_n$ can be written as
$$ f_n(X_1, ..., X_n) = binom{s+n-1}{n} + f_{n-1}(X_1, ldots, X_{n-1}), $$
with the conventions that $f_n(0,ldots, 0) = 0$ and $f_0 = 0$.
Claim: Fix $sin mathbb{N}$. Then $f_n$ induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_n} Big[ binom{s+n-1}{n}, binom{s+n}{n} -1Big], $$
where $[x,y]$ is the set of integers from $x$ to $y$, and if $s=0$, then the set on the right is $[0,0]$ by convention.
Proof of the claim. It is obviously true for $n=1$. Assume it is true for $n-1$. Let us show it is true for $n$.
For a fixed $s=X_1+...+X_n$, the value $t=X_1 + ldots + X_{n-1}$ can be anything from $0$ to $s$, depending on the value of $X_n$. Thus, by the hypothesis on $f_{n-1}$, it induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_{n-1}} Big[ 0, binom{s+n-1}{n-1} -1Big] $$
defined by $(X_1, ldots, X_n) mapsto f_{n-1}(X_1, ldots, X_{n-1})$.
Thus $f_n$ induces a bijection from the set on the left to the interval $Big[binom{s+n-1}{n}, binom{s+n-1}{n} + binom{s+n-1}{n-1}-1Big]$. Since $binom{s+n-1}{n} + binom{s+n-1}{n-1} = binom{s+n}{n}$, the claim is proved.
The fact that $f_n$ is a bijection from $mathbb{N}^n$ to $mathbb{N}$ then follows immediately from the claim.
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060811%2fconjecture-about-polynomials-f-n-in-mathbb-qx-1-dots-x-n-defining-bijection%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The diagonalization argument can indeed be generalized. Roughly, one can see all elements of $mathbb{N}$ appear in order by going through all hyperplanes $X_1+ldots+X_n = s$.
Now for the proof. Let $s=X_1+...+X_n$. Then your function $f_n$ can be written as
$$ f_n(X_1, ..., X_n) = binom{s+n-1}{n} + f_{n-1}(X_1, ldots, X_{n-1}), $$
with the conventions that $f_n(0,ldots, 0) = 0$ and $f_0 = 0$.
Claim: Fix $sin mathbb{N}$. Then $f_n$ induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_n} Big[ binom{s+n-1}{n}, binom{s+n}{n} -1Big], $$
where $[x,y]$ is the set of integers from $x$ to $y$, and if $s=0$, then the set on the right is $[0,0]$ by convention.
Proof of the claim. It is obviously true for $n=1$. Assume it is true for $n-1$. Let us show it is true for $n$.
For a fixed $s=X_1+...+X_n$, the value $t=X_1 + ldots + X_{n-1}$ can be anything from $0$ to $s$, depending on the value of $X_n$. Thus, by the hypothesis on $f_{n-1}$, it induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_{n-1}} Big[ 0, binom{s+n-1}{n-1} -1Big] $$
defined by $(X_1, ldots, X_n) mapsto f_{n-1}(X_1, ldots, X_{n-1})$.
Thus $f_n$ induces a bijection from the set on the left to the interval $Big[binom{s+n-1}{n}, binom{s+n-1}{n} + binom{s+n-1}{n-1}-1Big]$. Since $binom{s+n-1}{n} + binom{s+n-1}{n-1} = binom{s+n}{n}$, the claim is proved.
The fact that $f_n$ is a bijection from $mathbb{N}^n$ to $mathbb{N}$ then follows immediately from the claim.
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
$endgroup$
add a comment |
$begingroup$
The diagonalization argument can indeed be generalized. Roughly, one can see all elements of $mathbb{N}$ appear in order by going through all hyperplanes $X_1+ldots+X_n = s$.
Now for the proof. Let $s=X_1+...+X_n$. Then your function $f_n$ can be written as
$$ f_n(X_1, ..., X_n) = binom{s+n-1}{n} + f_{n-1}(X_1, ldots, X_{n-1}), $$
with the conventions that $f_n(0,ldots, 0) = 0$ and $f_0 = 0$.
Claim: Fix $sin mathbb{N}$. Then $f_n$ induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_n} Big[ binom{s+n-1}{n}, binom{s+n}{n} -1Big], $$
where $[x,y]$ is the set of integers from $x$ to $y$, and if $s=0$, then the set on the right is $[0,0]$ by convention.
Proof of the claim. It is obviously true for $n=1$. Assume it is true for $n-1$. Let us show it is true for $n$.
For a fixed $s=X_1+...+X_n$, the value $t=X_1 + ldots + X_{n-1}$ can be anything from $0$ to $s$, depending on the value of $X_n$. Thus, by the hypothesis on $f_{n-1}$, it induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_{n-1}} Big[ 0, binom{s+n-1}{n-1} -1Big] $$
defined by $(X_1, ldots, X_n) mapsto f_{n-1}(X_1, ldots, X_{n-1})$.
Thus $f_n$ induces a bijection from the set on the left to the interval $Big[binom{s+n-1}{n}, binom{s+n-1}{n} + binom{s+n-1}{n-1}-1Big]$. Since $binom{s+n-1}{n} + binom{s+n-1}{n-1} = binom{s+n}{n}$, the claim is proved.
The fact that $f_n$ is a bijection from $mathbb{N}^n$ to $mathbb{N}$ then follows immediately from the claim.
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
$endgroup$
add a comment |
$begingroup$
The diagonalization argument can indeed be generalized. Roughly, one can see all elements of $mathbb{N}$ appear in order by going through all hyperplanes $X_1+ldots+X_n = s$.
Now for the proof. Let $s=X_1+...+X_n$. Then your function $f_n$ can be written as
$$ f_n(X_1, ..., X_n) = binom{s+n-1}{n} + f_{n-1}(X_1, ldots, X_{n-1}), $$
with the conventions that $f_n(0,ldots, 0) = 0$ and $f_0 = 0$.
Claim: Fix $sin mathbb{N}$. Then $f_n$ induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_n} Big[ binom{s+n-1}{n}, binom{s+n}{n} -1Big], $$
where $[x,y]$ is the set of integers from $x$ to $y$, and if $s=0$, then the set on the right is $[0,0]$ by convention.
Proof of the claim. It is obviously true for $n=1$. Assume it is true for $n-1$. Let us show it is true for $n$.
For a fixed $s=X_1+...+X_n$, the value $t=X_1 + ldots + X_{n-1}$ can be anything from $0$ to $s$, depending on the value of $X_n$. Thus, by the hypothesis on $f_{n-1}$, it induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_{n-1}} Big[ 0, binom{s+n-1}{n-1} -1Big] $$
defined by $(X_1, ldots, X_n) mapsto f_{n-1}(X_1, ldots, X_{n-1})$.
Thus $f_n$ induces a bijection from the set on the left to the interval $Big[binom{s+n-1}{n}, binom{s+n-1}{n} + binom{s+n-1}{n-1}-1Big]$. Since $binom{s+n-1}{n} + binom{s+n-1}{n-1} = binom{s+n}{n}$, the claim is proved.
The fact that $f_n$ is a bijection from $mathbb{N}^n$ to $mathbb{N}$ then follows immediately from the claim.
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
$endgroup$
The diagonalization argument can indeed be generalized. Roughly, one can see all elements of $mathbb{N}$ appear in order by going through all hyperplanes $X_1+ldots+X_n = s$.
Now for the proof. Let $s=X_1+...+X_n$. Then your function $f_n$ can be written as
$$ f_n(X_1, ..., X_n) = binom{s+n-1}{n} + f_{n-1}(X_1, ldots, X_{n-1}), $$
with the conventions that $f_n(0,ldots, 0) = 0$ and $f_0 = 0$.
Claim: Fix $sin mathbb{N}$. Then $f_n$ induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_n} Big[ binom{s+n-1}{n}, binom{s+n}{n} -1Big], $$
where $[x,y]$ is the set of integers from $x$ to $y$, and if $s=0$, then the set on the right is $[0,0]$ by convention.
Proof of the claim. It is obviously true for $n=1$. Assume it is true for $n-1$. Let us show it is true for $n$.
For a fixed $s=X_1+...+X_n$, the value $t=X_1 + ldots + X_{n-1}$ can be anything from $0$ to $s$, depending on the value of $X_n$. Thus, by the hypothesis on $f_{n-1}$, it induces a bijection
$$ Big{ (X_1, ldots, X_n)in mathbb{N}^n | s=X_1+...+X_n Big} xrightarrow{f_{n-1}} Big[ 0, binom{s+n-1}{n-1} -1Big] $$
defined by $(X_1, ldots, X_n) mapsto f_{n-1}(X_1, ldots, X_{n-1})$.
Thus $f_n$ induces a bijection from the set on the left to the interval $Big[binom{s+n-1}{n}, binom{s+n-1}{n} + binom{s+n-1}{n-1}-1Big]$. Since $binom{s+n-1}{n} + binom{s+n-1}{n-1} = binom{s+n}{n}$, the claim is proved.
The fact that $f_n$ is a bijection from $mathbb{N}^n$ to $mathbb{N}$ then follows immediately from the claim.
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
answered Jan 4 at 12:30
Pierre-Guy PlamondonPierre-Guy Plamondon
8,79511639
8,79511639
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060811%2fconjecture-about-polynomials-f-n-in-mathbb-qx-1-dots-x-n-defining-bijection%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
