Probability that $x^2+y^2+z^2=0$ mod $p$
This question on MSE asked the following:
"Given $x,y,z in mathbb{N},$ find probability that $x^2+y^2+z^2$ is divisible by $7.$"
The OP did not declare the assumed probability model, and was duly criticised for that. On the other hand, it is only natural to assume that $x$, $y$, $z$ are independently uniformly distributed mod $7$.
A case analysis then shows that that the probability in question is ${1over7}$. This simple result led me to solve the same problem for the primes $p=3$, $5$, $11$, and $13$. In each case I obtained ${1over p}$ as result. Further experiments showed that the remainder of $s=x^2+y^2+z^2$ mod $p$ is not uniformly distributed mod $p$, but that in any case the probability of $s=0$ mod $p$ is equal to ${1over p}$ for all $pleq107$. This leads to the following
Conjecture. Let the integeres $x$, $y$, $z$ be independently uniformly distributed modulo the prime $p$. Then the probability that $s:=x^2+y^2+z^2$ is divisible by $p$ is equal to ${1over p}$.
Maybe this well known. Otherwise I'd like to see a proof.
elementary-number-theory
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
add a comment |
This question on MSE asked the following:
"Given $x,y,z in mathbb{N},$ find probability that $x^2+y^2+z^2$ is divisible by $7.$"
The OP did not declare the assumed probability model, and was duly criticised for that. On the other hand, it is only natural to assume that $x$, $y$, $z$ are independently uniformly distributed mod $7$.
A case analysis then shows that that the probability in question is ${1over7}$. This simple result led me to solve the same problem for the primes $p=3$, $5$, $11$, and $13$. In each case I obtained ${1over p}$ as result. Further experiments showed that the remainder of $s=x^2+y^2+z^2$ mod $p$ is not uniformly distributed mod $p$, but that in any case the probability of $s=0$ mod $p$ is equal to ${1over p}$ for all $pleq107$. This leads to the following
Conjecture. Let the integeres $x$, $y$, $z$ be independently uniformly distributed modulo the prime $p$. Then the probability that $s:=x^2+y^2+z^2$ is divisible by $p$ is equal to ${1over p}$.
Maybe this well known. Otherwise I'd like to see a proof.
elementary-number-theory
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $Bbb N$.
– Masacroso
Feb 27 '17 at 20:38
so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation....
– Will Jagy
Feb 27 '17 at 20:47
add a comment |
This question on MSE asked the following:
"Given $x,y,z in mathbb{N},$ find probability that $x^2+y^2+z^2$ is divisible by $7.$"
The OP did not declare the assumed probability model, and was duly criticised for that. On the other hand, it is only natural to assume that $x$, $y$, $z$ are independently uniformly distributed mod $7$.
A case analysis then shows that that the probability in question is ${1over7}$. This simple result led me to solve the same problem for the primes $p=3$, $5$, $11$, and $13$. In each case I obtained ${1over p}$ as result. Further experiments showed that the remainder of $s=x^2+y^2+z^2$ mod $p$ is not uniformly distributed mod $p$, but that in any case the probability of $s=0$ mod $p$ is equal to ${1over p}$ for all $pleq107$. This leads to the following
Conjecture. Let the integeres $x$, $y$, $z$ be independently uniformly distributed modulo the prime $p$. Then the probability that $s:=x^2+y^2+z^2$ is divisible by $p$ is equal to ${1over p}$.
Maybe this well known. Otherwise I'd like to see a proof.
elementary-number-theory
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
This question on MSE asked the following:
"Given $x,y,z in mathbb{N},$ find probability that $x^2+y^2+z^2$ is divisible by $7.$"
The OP did not declare the assumed probability model, and was duly criticised for that. On the other hand, it is only natural to assume that $x$, $y$, $z$ are independently uniformly distributed mod $7$.
A case analysis then shows that that the probability in question is ${1over7}$. This simple result led me to solve the same problem for the primes $p=3$, $5$, $11$, and $13$. In each case I obtained ${1over p}$ as result. Further experiments showed that the remainder of $s=x^2+y^2+z^2$ mod $p$ is not uniformly distributed mod $p$, but that in any case the probability of $s=0$ mod $p$ is equal to ${1over p}$ for all $pleq107$. This leads to the following
Conjecture. Let the integeres $x$, $y$, $z$ be independently uniformly distributed modulo the prime $p$. Then the probability that $s:=x^2+y^2+z^2$ is divisible by $p$ is equal to ${1over p}$.
Maybe this well known. Otherwise I'd like to see a proof.
elementary-number-theory
elementary-number-theory
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
edited Apr 13 '17 at 12:20
Community♦
1
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
asked Feb 27 '17 at 20:34
Christian Blatter
172k7112326
172k7112326
If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $Bbb N$.
– Masacroso
Feb 27 '17 at 20:38
so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation....
– Will Jagy
Feb 27 '17 at 20:47
add a comment |
If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $Bbb N$.
– Masacroso
Feb 27 '17 at 20:38
so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation....
– Will Jagy
Feb 27 '17 at 20:47
If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $Bbb N$.
– Masacroso
Feb 27 '17 at 20:38
If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $Bbb N$.
– Masacroso
Feb 27 '17 at 20:38
so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation....
– Will Jagy
Feb 27 '17 at 20:47
so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation....
– Will Jagy
Feb 27 '17 at 20:47
add a comment |
1 Answer
1
active
oldest
votes
Found it. Given odd dimension $n$ and quadratic form
$$ f = a_1 x_1^2 + a_2 x_2^2 + cdots + a_n x_n^2, $$
everything in a finite field with odd number of elements $q,$ the count
$$ #left(f = bright) ; = ; q^{n-1} + q^{(n-1)/2} ; ; chi left( ; (-1)^{(n-1)/2} ; b a_1 a_2 ldots a_nright). $$ At the bottom of page 91 Small points out that
$$ #left(f = 0right) ; = ; q^{n-1} . $$
When $b neq 0$ we need to know what $chi$ means.
Aah. Page 86, very simple. We have finite field $F$ and element $a.$ First $chi(0) = 0.$ If $a$ is a nonzero square, $chi(a)=1.$ If $a$ is nonzero and not a square, $chi(a)=-1.$
Charles Small, Arithmetic of Finite Fields, Theorem 4.6 on page 91,
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
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%2f2164308%2fprobability-that-x2y2z2-0-mod-p%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
Found it. Given odd dimension $n$ and quadratic form
$$ f = a_1 x_1^2 + a_2 x_2^2 + cdots + a_n x_n^2, $$
everything in a finite field with odd number of elements $q,$ the count
$$ #left(f = bright) ; = ; q^{n-1} + q^{(n-1)/2} ; ; chi left( ; (-1)^{(n-1)/2} ; b a_1 a_2 ldots a_nright). $$ At the bottom of page 91 Small points out that
$$ #left(f = 0right) ; = ; q^{n-1} . $$
When $b neq 0$ we need to know what $chi$ means.
Aah. Page 86, very simple. We have finite field $F$ and element $a.$ First $chi(0) = 0.$ If $a$ is a nonzero square, $chi(a)=1.$ If $a$ is nonzero and not a square, $chi(a)=-1.$
Charles Small, Arithmetic of Finite Fields, Theorem 4.6 on page 91,
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
add a comment |
Found it. Given odd dimension $n$ and quadratic form
$$ f = a_1 x_1^2 + a_2 x_2^2 + cdots + a_n x_n^2, $$
everything in a finite field with odd number of elements $q,$ the count
$$ #left(f = bright) ; = ; q^{n-1} + q^{(n-1)/2} ; ; chi left( ; (-1)^{(n-1)/2} ; b a_1 a_2 ldots a_nright). $$ At the bottom of page 91 Small points out that
$$ #left(f = 0right) ; = ; q^{n-1} . $$
When $b neq 0$ we need to know what $chi$ means.
Aah. Page 86, very simple. We have finite field $F$ and element $a.$ First $chi(0) = 0.$ If $a$ is a nonzero square, $chi(a)=1.$ If $a$ is nonzero and not a square, $chi(a)=-1.$
Charles Small, Arithmetic of Finite Fields, Theorem 4.6 on page 91,
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
add a comment |
Found it. Given odd dimension $n$ and quadratic form
$$ f = a_1 x_1^2 + a_2 x_2^2 + cdots + a_n x_n^2, $$
everything in a finite field with odd number of elements $q,$ the count
$$ #left(f = bright) ; = ; q^{n-1} + q^{(n-1)/2} ; ; chi left( ; (-1)^{(n-1)/2} ; b a_1 a_2 ldots a_nright). $$ At the bottom of page 91 Small points out that
$$ #left(f = 0right) ; = ; q^{n-1} . $$
When $b neq 0$ we need to know what $chi$ means.
Aah. Page 86, very simple. We have finite field $F$ and element $a.$ First $chi(0) = 0.$ If $a$ is a nonzero square, $chi(a)=1.$ If $a$ is nonzero and not a square, $chi(a)=-1.$
Charles Small, Arithmetic of Finite Fields, Theorem 4.6 on page 91,
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
Found it. Given odd dimension $n$ and quadratic form
$$ f = a_1 x_1^2 + a_2 x_2^2 + cdots + a_n x_n^2, $$
everything in a finite field with odd number of elements $q,$ the count
$$ #left(f = bright) ; = ; q^{n-1} + q^{(n-1)/2} ; ; chi left( ; (-1)^{(n-1)/2} ; b a_1 a_2 ldots a_nright). $$ At the bottom of page 91 Small points out that
$$ #left(f = 0right) ; = ; q^{n-1} . $$
When $b neq 0$ we need to know what $chi$ means.
Aah. Page 86, very simple. We have finite field $F$ and element $a.$ First $chi(0) = 0.$ If $a$ is a nonzero square, $chi(a)=1.$ If $a$ is nonzero and not a square, $chi(a)=-1.$
Charles Small, Arithmetic of Finite Fields, Theorem 4.6 on page 91,
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
edited Nov 27 '18 at 20:28
Lorenzo B.
1,8322520
1,8322520
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
answered Feb 27 '17 at 20:55
Will Jagy
101k599199
101k599199
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f2164308%2fprobability-that-x2y2z2-0-mod-p%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
If the conjecture is true this probably means that $w:=x^2+y^2+z^2$ is and uniformly distributed random variable in $Bbb N$.
– Masacroso
Feb 27 '17 at 20:38
so far, this is part of theorem 4.12 in Charles Small, Arithmetic of Finite Fields. Alright, it is exactly theorem 4.6 on page 91, need notation....
– Will Jagy
Feb 27 '17 at 20:47