User ravi boppana - MathOverflow

Answer by Ravi Boppana for Examples of common false beliefs in mathematics.

2010-05-05T01:00:50Z

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.)

Much later edit: As pointed out elsewhere in this thread, Euclid's proof is not by contradiction; that is another widespread false belief.

Much much later edit: 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 is a proof by contradiction. Euclid says (Elements Book 9 Proposition 20): The very thing (is) absurd. Thus, G is not the same as one of A, B, C. And it was assumed (to be) prime.

Nb. The above edits were not added by the OP of this answer.

Answer by Ravi Boppana for Missing mass conjecture

2011-04-05T21:40:09Z

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 The Cauchy-Schwarz Master Class.) Applying Jensen's inequality, we have $\sum f(p_i) \le \sum g(p_i) \le n g(1/n)$.

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.

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.

Answer by Ravi Boppana for Guessing a subset of {1,...,N}

2011-03-16T03:27:19Z

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:

B. Lindstrom (1964), "On a combinatory detection problem I", Mathematical Institute of the Hungarian Academy of Science 9, pp. 195-207.

B. Lindstrom (1965), "On a combinatorial problem in number theory", Canadian Math. Bulletin 8, pp. 477-490.

D. Cantor and W. Mills (1966), "Determining a subset from certain combinatorial properties", Canadian J. Math 18, pp. 42-48.

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:

M. Aigner (1988), "Combinatorial search", John Wiley and Sons.

Answer by Ravi Boppana for Diophantine equation with no integer solutions, but with solutions modulo every integer

2011-01-01T23:22:56Z

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.

Answer by Ravi Boppana for Untrustworthy people picking a random number

2010-08-14T22:23:31Z

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.

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:

M. Saks (1989), A robust non-cryptographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics 2, pages 240-244.

M. Ajtai and N. Linial (1993), The influence of large coalitions, Combinatorica 13, pages 129-145.

You can find a scanned copy of the Ajtai-Linial paper at Linial's homepage: http://www.cs.huji.ac.il/~nati/.

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:

R. Boppana and B. Narayanan (2000), Perfect-Information Leader Election with Optimal Resilience, SIAM Journal on Computing 29:4, pages 1304-1320.

Answer by Ravi Boppana for Choosing lines and points in D^2

2010-07-16T12:12:53Z

Line actually has a winning strategy: it can force a convergent sequence. The problem was posed and solved in the following paper:

J. Maly and M. Zeleny (2006), A note on Buczolich's solution of the Weil gradient problem: a construction based on an infinite game, Acta Mathematica Hungarica, Vol. 113, pp. 145-158.

Answer by Ravi Boppana for The probabilistic method - reference to less challenging questions

2010-07-13T22:37:44Z

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 here.

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.

Answer by Ravi Boppana for Examples of common false beliefs in mathematics.

2010-06-06T19:42:52Z

I once thought that if $A$, $B$, $C$, and $D$ were $n$-by-$n$ matrices, then the determinant of the block matrix $\pmatrix{A & B \\ C & D}$ would be $\det(A) \det(D) - \det(B) \det(C)$.

Answer by Ravi Boppana for What is the nonrecursive formula for the following implicit function?

2010-04-14T21:34:05Z

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.

Answer by Ravi Boppana for Strong induction without a base case

2010-01-21T12:38:03Z

@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$.

Answer by Ravi Boppana for Strong induction without a base case

2010-01-19T03:04:01Z

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$.

Comment by Ravi Boppana

2010-12-01T16:46:04Z

My father-in-law, an engineer, thought that $\pi$ was $22/7$ until I explained to him otherwise.

Comment by Ravi Boppana

2010-09-03T14:01:50Z

Nitpick: The title of Guy's paper is "The Strong Law of Small Numbers".

Comment by Ravi Boppana

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$.

Comment by Ravi Boppana

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.

Comment by Ravi Boppana

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?

Comment by Ravi Boppana

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.

Comment by Ravi Boppana

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 < 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.