User ravi boppana - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:35:21Z http://mathoverflow.net/feeds/user/3376 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/23521#23521 Answer by Ravi Boppana for Examples of common false beliefs in mathematics. Ravi Boppana 2010-05-05T01:00:50Z 2013-04-16T19:41:59Z <p>Many students believe that 1 plus the product of the first $n$ primes is always a prime number. They have misunderstood the contradiction in Euclid's proof that there are infinitely many primes. (By the way, 2 * 3 * 5 * 7 * 11 * 13 + 1 is not prime.) </p> <p><b>Much later edit:</b> As pointed out elsewhere in this thread, Euclid's proof is not by contradiction; that is another widespread false belief.</p> <p><b>Much much later edit:</b> Euclid's proof is not not by contradiction. This is another very widespread false belief. It depends on personal opinion and interpretation what a proof by contradiction is and whether Euclid's proof belongs to this category. In fact, if the derivation of an absurdity or the contradiction of an assumption is a proof by contradiction, then Euclid's proof <em>is</em> a proof by contradiction. Euclid says (Elements Book 9 Proposition 20): <em>The very thing (is) absurd. Thus, G is not the same as one of A, B, C. And it was assumed (to be) prime.</em></p> <p><hr> <b>Nb.</b> The above edits were not added by the OP of this answer.</p> http://mathoverflow.net/questions/60722/missing-mass-conjecture/60747#60747 Answer by Ravi Boppana for Missing mass conjecture Ravi Boppana 2011-04-05T21:40:09Z 2011-04-07T02:21:43Z <p>Since the single-variable optimization that David mentions still requires some work, I will present another solution. Let $f(p) = p(1-p)^t$. Define the function $g$ that is equal to $f$ on $[0, 1/t]$, and on $[1/t, 1]$ is a linear interpolation between the points $(1/t, f(1/t))$ and $(1, 0)$. Then we can check that $g$ is concave on all of $[0, 1]$ and $g \ge f$ on all of $[0, 1]$. (I learned this concept of "concave majorants" or "convex minorants" from Steele's book called <em>The Cauchy-Schwarz Master Class</em>.) Applying Jensen's inequality, we have $\sum f(p_i) \le \sum g(p_i) \le n g(1/n)$.</p> <p>We now split into two cases, $t \le n -1$ or $t \ge n$. First, suppose that $t \le n - 1$. Then $g(1/n) = f(1/n) = (1/n) (1 - 1/n)^t$. So we need to show that $(1 - 1/n)^t$ is at most $n (1 - 1/n)^n / t$. That's equivalent to showing $t(1 - 1/n)^t \le n (1 - 1/n)^n$. We can check that the left side is an increasing function of $t$ for $t \le n - 1$, and when $t = n - 1$ we have an equality. So we have established the inequality in this case.</p> <p>Next suppose that $t \ge n$. Then by linear interpolation, we find $g(1/n) = (1 - 1/t)^{t-1} (1 - 1/n) / t$. So we need to show that $(1 - 1/t)^{t - 1} (n - 1) \le n(1 - 1/n)^n$. That's equivalent to $(1 - 1/t)^{t-1} \le (1 - 1/n)^{n - 1}$. By taking reciprocals, that's equivalent to $(1 + 1/(t - 1))^{t - 1} \ge (1 + 1/(n-1))^{n - 1}$. The left side is an increasing function of $t$, and we have an equality when $t = n$. So we have established the inequality in the second case too. </p> http://mathoverflow.net/questions/58600/guessing-a-subset-of-1-n/58607#58607 Answer by Ravi Boppana for Guessing a subset of {1,...,N} Ravi Boppana 2011-03-16T03:27:19Z 2011-03-16T03:27:19Z <p>This is a well-studied problem, sometimes phrased as a coin-weighing problem. It is known that $g(N)$ is $O(N / \log N)$. (We can even specify the guessing sets in advance, without knowing the previous answers.) I believe these three papers are the earliest to show this bound:</p> <p>B. Lindstrom (1964), "On a combinatory detection problem I", <em>Mathematical Institute of the Hungarian Academy of Science</em> 9, pp. 195-207.</p> <p>B. Lindstrom (1965), "On a combinatorial problem in number theory", <em>Canadian Math. Bulletin</em> 8, pp. 477-490.</p> <p>D. Cantor and W. Mills (1966), "Determining a subset from certain combinatorial properties", <em>Canadian J. Math</em> 18, pp. 42-48.</p> <p>There was a lot of work after these papers too (some with simpler constructions, some to solve more general problems). A book by Aigner covers this topic and more:</p> <p>M. Aigner (1988), "Combinatorial search", John Wiley and Sons.</p> http://mathoverflow.net/questions/47442/diophantine-equation-with-no-integer-solutions-but-with-solutions-modulo-every-i/50887#50887 Answer by Ravi Boppana for Diophantine equation with no integer solutions, but with solutions modulo every integer Ravi Boppana 2011-01-01T23:22:56Z 2011-01-01T23:22:56Z <p>Consider the equation $(2x - 1)(3x - 1) = 0$. This equation has no integer solutions. But modulo $n$, it always has a solution. If $n$ is not a multiple of $2$, we can make $2x -1$ a multiple of $n$. If $n$ is not a multiple of $3$, we can make $3x - 1$ a multiple of $n$. Using the Chinese Remainder Theorem, we can handle every other $n$ by piecing together these two solutions.</p> http://mathoverflow.net/questions/35382/untrustworthy-people-picking-a-random-number/35605#35605 Answer by Ravi Boppana for Untrustworthy people picking a random number Ravi Boppana 2010-08-14T22:23:31Z 2010-08-14T22:23:31Z <p>If the final outcome doesn't need to be perfectly unbiased, but instead may have a bias of up to say 10 percent, then there are good algorithms, even if the people have unlimited computational power (which renders cryptographic methods ineffective). For example, the following baton-passing algorithm works well. At the start, give the baton to an arbitrary person (say the first person). At each step, the current baton-holder gives the baton to a random person who has not yet held the baton. Whoever receives the baton last gets to make the collective coin flip.</p> <p>If the number of saboteurs is fewer than $n / \log n$, then this algorithm is known to produce a low-biased coin. Mike Saks proposed and analyzed this algorithm, and Miki Ajtai and Nati Linial refined the analysis. Here are the references:</p> <p>M. Saks (1989), A robust non-cryptographic protocol for collective coin flipping, <em>SIAM Journal on Discrete Mathematics</em> 2, pages 240-244.</p> <p>M. Ajtai and N. Linial (1993), The influence of large coalitions, <em>Combinatorica</em> 13, pages 129-145.</p> <p>You can find a scanned copy of the Ajtai-Linial paper at Linial's homepage: <a href="http://www.cs.huji.ac.il/~nati/" rel="nofollow">http://www.cs.huji.ac.il/~nati/</a>. </p> <p>Babu Narayanan and I showed that there exists an algorithm that can handle up to 49 percent of the players being saboteurs and yet still produces a low-biased coin. Here is the reference:</p> <p>R. Boppana and B. Narayanan (2000), Perfect-Information Leader Election with Optimal Resilience, <em>SIAM Journal on Computing</em> 29:4, pages 1304-1320.</p> http://mathoverflow.net/questions/31936/choosing-lines-and-points-in-d2/32159#32159 Answer by Ravi Boppana for Choosing lines and points in D^2 Ravi Boppana 2010-07-16T12:12:53Z 2010-07-17T10:50:22Z <p>Line actually has a winning strategy: it can force a convergent sequence. The problem was posed and solved in the following paper:</p> <p>J. Maly and M. Zeleny (2006), A note on Buczolich's solution of the Weil gradient problem: a construction based on an infinite game, <a href="http://dx.doi.org/10.1007/s10474-006-0096-7" rel="nofollow"><em>Acta Mathematica Hungarica</em>, Vol. 113, pp. 145-158.</a></p> http://mathoverflow.net/questions/31760/the-probabilistic-method-reference-to-less-challenging-questions/31771#31771 Answer by Ravi Boppana for The probabilistic method - reference to less challenging questions Ravi Boppana 2010-07-13T22:37:44Z 2010-07-13T22:37:44Z <p>I gave a couple of lectures to some bright high-school students on the probabilistic method. For the lectures, I created a handout of 38 problems with hints at the end. The link is <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1943887#p1943887" rel="nofollow">here</a>. </p> <p>I wouldn't say the problems are easy (many come from olympiads), but maybe some will suit your purposes, especially if you provide the hints. </p> http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/27269#27269 Answer by Ravi Boppana for Examples of common false beliefs in mathematics. Ravi Boppana 2010-06-06T19:42:52Z 2010-06-06T19:42:52Z <p>I once thought that if $A$, $B$, $C$, and $D$ were $n$-by-$n$ matrices, then the determinant of the block matrix $\pmatrix{A &amp; B \\ C &amp; D}$ would be $\det(A) \det(D) - \det(B) \det(C)$.</p> http://mathoverflow.net/questions/21386/what-is-the-nonrecursive-formula-for-the-following-implicit-function/21392#21392 Answer by Ravi Boppana for What is the nonrecursive formula for the following implicit function? Ravi Boppana 2010-04-14T21:34:05Z 2010-04-14T21:34:05Z <p>We can rewrite the given recurrence as $(f(n) - 2)(f(n-1) - 2) = 2$. That makes it clear that the sequence is 2-periodic.</p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12534#12534 Answer by Ravi Boppana for Strong induction without a base case Ravi Boppana 2010-01-21T12:38:03Z 2010-01-21T12:38:03Z <p>@steve: I'm not sure I understand your objection, but how about this modification. Let A be defined by $A(n) = \sum_{k=0}^{n-1} A(k)$ for every nonnegative integer n. Then by strong induction we can show that A(n) = 0. That's a trivial example, but if we wanted to, we could make it less trivial: $B(n) = 1 - n + \sum_{k=0}^{n-1} B(k)$, which has solution $B(n) = 1$. </p> http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12270#12270 Answer by Ravi Boppana for Strong induction without a base case Ravi Boppana 2010-01-19T03:04:01Z 2010-01-19T03:04:01Z <p>Here's another possible example. Let S(0), S(1), S(2), ..., be the sequence of numbers defined by the formula $S(n) = 1 + \sum_{k=0}^{n-1} S(k)$ for every nonnegative integer n. Then we can show that $S(n) = 2^n$ by strong induction on $n$.</p> http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/47515#47515 Comment by Ravi Boppana Ravi Boppana 2010-12-01T16:46:04Z 2010-12-01T16:46:04Z My father-in-law, an engineer, thought that $\pi$ was $22/7$ until I explained to him otherwise. http://mathoverflow.net/questions/37610/demonstrating-that-rigour-is-important/37611#37611 Comment by Ravi Boppana Ravi Boppana 2010-09-03T14:01:50Z 2010-09-03T14:01:50Z Nitpick: The title of Guy's paper is &quot;The Strong Law of <i>Small</i> Numbers&quot;. http://mathoverflow.net/questions/36797/trosts-discriminant-trick Comment by Ravi Boppana Ravi Boppana 2010-08-26T22:55:08Z 2010-08-26T22:55:08Z Even simpler, if $a^4 - 2b^2 = 1$, then $a^4 + b^4 = (2b^2 + 1) + b^4 = (b^2 + 1)^2$. http://mathoverflow.net/questions/36797/trosts-discriminant-trick Comment by Ravi Boppana Ravi Boppana 2010-08-26T19:48:00Z 2010-08-26T19:48:00Z That's a neat trick. Here's another way of looking at it. I'll use the identity $a^4 + b^4 = (a^4 - b^2)^2 - a^4(a^4 - 2b^2 - 1)$. Hence if $a^4 - 2b^2 = 1$, it follows that $a^4 + b^4$ is a square. http://mathoverflow.net/questions/31262/smallest-dilation-of-a-quadrilateral Comment by Ravi Boppana Ravi Boppana 2010-07-12T11:20:58Z 2010-07-12T11:20:58Z This problem looks interesting, but I'm a little confused by the definitions. In the definition of $\delta(x, y)$, what are we taking the maximum over? In the definition of $\delta(P)$, did you mean maximum, not minimum? http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/23521#23521 Comment by Ravi Boppana Ravi Boppana 2010-05-05T02:59:55Z 2010-05-05T02:59:55Z @Daniel: Sorry to hear that. When my daughter Meena was the same age (11), her teacher asserted that 0.999... was not equal to 1. Meena supplied one or two proofs that they were equal, but her teacher would not budge. Maybe this is another example of a common false belief. http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/12270#12270 Comment by Ravi Boppana Ravi Boppana 2010-01-21T13:59:40Z 2010-01-21T13:59:40Z Here is the proof by strong induction I had in mind. Suppose by strong induction that $S(k) = 2^k$ for all $k &lt; n$. Then $S(n) = 1 + \sum_{k=0}^{n-1} S(k) = 1 + \sum_{k=0}^{n-1} 2^k = 1 + (2^n - 1) = 2^n$. (The third equation is using the usual formula for geometric series.) The proof seems to be using strong induction, not weak induction. I don't think I needed to handle n = 0 separately. If you'd rather avoid the appeal to the formula for geometric series, then the examples in my other answer might be better.