Counting lattice points with relatively prime coordinates The Next CEO of Stack...
Can this transistor (2N2222) take 6 V on emitter-base? Am I reading the datasheet incorrectly?
How to unfasten electrical subpanel attached with ramset
How seriously should I take size and weight limits of hand luggage?
Is it possible to create a QR code using text?
Compensation for working overtime on Saturdays
logical reads on global temp table, but not on session-level temp table
Salesforce opportunity stages
How dangerous is XSS
What difference does it make matching a word with/without a trailing whitespace?
Finitely generated matrix groups whose eigenvalues are all algebraic
Is it a bad idea to plug the other end of ESD strap to wall ground?
How should I connect my cat5 cable to connectors having an orange-green line?
Is it okay to majorly distort historical facts while writing a fiction story?
My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?
Direct Implications Between USA and UK in Event of No-Deal Brexit
How does a dynamic QR code work?
Does Germany produce more waste than the US?
How to pronounce fünf in 45
Why can't we say "I have been having a dog"?
Man transported from Alternate World into ours by a Neutrino Detector
Why doesn't Shulchan Aruch include the laws of destroying fruit trees?
What did the word "leisure" mean in late 18th Century usage?
Is it correct to say moon starry nights?
How can the PCs determine if an item is a phylactery?
Counting lattice points with relatively prime coordinates
The Next CEO of Stack OverflowCounting Lattice Points with Ehrhart PolynomialsFinding a set of subsets such that for each such subset in the set, there exists another subset in the same set which is non-disjointConcise proof that every common divisor divides GCD without Bezout's identity?counting lattice paths with turnsFind the condition for a center of a circle with exactly one lattice point on its circumferenceUnderstanding the proof of unique natural divisorConditions for $(I+K)cap (J+K) = Icap J +K $ to hold for ideals of ring $R$Probabilistic/combinatoric proof of $sum_{k=0}^{n}binom{tk+r}{k}binom{t(n-k)+s}{n-k}frac{r}{tk+r}=binom{tn+r+s}{n}$A proof of a simple combinatorial lemmaCounting Lattice Points
$begingroup$
My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.
Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
, : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
$$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
gcd(x,y) = 1, text{ and } x+y > n}$$ Then, we have $|S| = |R| + 1$.
Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$
We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.
Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$
combinatorics elementary-number-theory
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
$endgroup$
add a comment |
$begingroup$
My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.
Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
, : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
$$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
gcd(x,y) = 1, text{ and } x+y > n}$$ Then, we have $|S| = |R| + 1$.
Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$
We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.
Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$
combinatorics elementary-number-theory
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
$endgroup$
add a comment |
$begingroup$
My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.
Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
, : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
$$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
gcd(x,y) = 1, text{ and } x+y > n}$$ Then, we have $|S| = |R| + 1$.
Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$
We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.
Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$
combinatorics elementary-number-theory
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
$endgroup$
My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.
Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
, : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
$$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
gcd(x,y) = 1, text{ and } x+y > n}$$ Then, we have $|S| = |R| + 1$.
Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$
We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.
Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$
combinatorics elementary-number-theory
combinatorics elementary-number-theory
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
edited Mar 18 at 2:09
Sameer Kailasa
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
asked Mar 18 at 1:32
Sameer KailasaSameer Kailasa
5,59321843
5,59321843
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A heuristic start:
Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
$endgroup$
add a comment |
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%2f3152297%2fcounting-lattice-points-with-relatively-prime-coordinates%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$
A heuristic start:
Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
$endgroup$
add a comment |
$begingroup$
A heuristic start:
Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
$endgroup$
add a comment |
$begingroup$
A heuristic start:
Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
$endgroup$
A heuristic start:
Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
answered Mar 18 at 13:15
Roddy MacPheeRoddy MacPhee
629118
629118
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%2f3152297%2fcounting-lattice-points-with-relatively-prime-coordinates%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
