Reputation
1,052
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
1 15 27
Newest
 Tumbleweed
Impact
~39k people reached

Apr
21
accepted Expectation of the fraction a random function covers its range
Apr
21
asked Expectation of the fraction a random function covers its range
Apr
16
awarded  Tumbleweed
Apr
9
asked Modular arithmetic involving real numbers
Mar
24
revised Help on notation: $\mathbb{Z}/n\mathbb{Z}$ vs. $\mathbb{Z}_n$
added 7 characters in body
Mar
22
accepted Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k
Mar
22
awarded  Yearling
Mar
21
comment Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k
For p=2 (i.e., when p is not odd), the function f(x) can be 4-to-1 (when k>=3). Can we consider this case as well, using your simple counting argument?
Mar
21
comment Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k
Thanks a lot. But I think you're actually following Hensel's lemma, without naming it. This is the constructive method which iteratively builds the solutions from the ground up.
Mar
21
comment Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k
@MXYMXY: Actually, it depends on how deep your studies are in number theory. The proof of lemma, especially when we are not dealing with $p$-adic numbers, seems pretty elementary to me, too. But as I'm going to describe it to some undergrad students, I wanted to check out if there's actually a simpler proof.
Mar
21
asked Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k
Mar
20
comment Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$?
@EricNaslund: Thanks for the response. As I wrote in my comment, I built up my argument around the assumption that "$O(\cdot)$ is positive." If $O\left(\frac{n}{(\log \log n)^2}\right)$ is meant to capture a negative quantity (which is allowed under the definition of big-$O$), then everything adds up.
Mar
20
comment Proving a combinatorial identity without double counting
Great. I always loved your answers; they're so inspiring!
Mar
20
comment Proving a combinatorial identity without double counting
Thanks for elaboration. I assume this corresponds to (and further formalizes) counting method 1 in the question, right?
Mar
20
comment Proving a combinatorial identity without double counting
@AndréNicolas: Could you please elaborate? My understanding is that per each ball, one assigns an indicator r.v., which is 1 is the ball is picked in the sample, and 0 otherwise. Did I get it right?
Mar
20
comment Proving a combinatorial identity without double counting
+1. This answer taught me a lot, thanks! But I'll wait to see if a more "elementary" answer shows up.
Mar
19
revised Proving a combinatorial identity without double counting
added 24 characters in body
Mar
19
asked Proving a combinatorial identity without double counting
Mar
19
comment Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$?
Sorry to bump an old topic, but I think something doesn't add up (though by my lack of experience, I might be mistaken). The inequality $\varphi(n)\geq \frac{n}{e^{\gamma}\log \log n}$ follows from the theorem you stated, assuming $O(\cdot)$ is positive. But Nicolas proved that this inequality does not hold for infinitely many $n$'s. The correct form of the theorem seems to be $\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$, see en.wikipedia.org/wiki/Euler%27s_totient_function#Growth_rate.
Feb
23
awarded  Popular Question