User drvitek - MathOverflow

Answer by drvitek for Surprising and Useful Physical Intuition for Mathematical Objects

2011-03-29T22:59:57Z

I don't know if you've heard of this before, but there is an extremely elegant physical proof of the existence and properties of the Fermat point. It even illustrates the degeneracy that starts to occur for largest angle at least $2\pi/3$.

Consider your desired triangle as a flat, sturdy, sheet. Make very small notches at the vertices. Now take three ideal ropes and at one end of each fix identical balls. Join all three free ends. Place the rope-ball configuration on the top of the triangle, and slide each of the ropes through the notches. Let the balls hang off the triangle.

Now, allow the system to assume its minimal potential energy. The intersection of the ropes will move to minimize the sum of the distances to the vertices, as potential energy is linear in height. So the intersection will move to the Fermat point.

But here is the tricky part. As the intersection stabilizes, we know that the forces on it must be zero. The forces all have the same magnitude, so if they are all zero then they must have equal angles between them. So the lines from the Fermat point X to the vertices of triangle ABC satisfy $\angle AXB = \angle BXC = \angle CXA = 2\pi/3$.

Of course, this suggests that in a suitably obtuse triangle the intersection will fall right through one of the notches, and indeed for angles greater than $2\pi/3$ the Fermat point is at the largest angle.

Answer by drvitek for Hanging a ball with string

2010-10-27T14:56:34Z

There is another stable solution of total length $3\pi + h + \epsilon$ for any $\epsilon > 0$. We take a circle of constant latitude $\delta < 0$ (sufficiently small) and then connect this circle to the north pole via two diametrically opposed strings. This is then clearly stable. Furthermore this is equivalent to your solution (plus Scott Carnahan's epsilon-modification).

However, there is in fact a stable solution of total string-length $2\pi+h+\epsilon$. We simply take the almost-equatorial circle in the last solution and drag it to the south pole, so that we have a small circle there along with two diametrically opposed support strings connecting it to the north pole. This solution is (barely) stable, although physically it is not exactly easy to implement (a very small but non-negligible disturbance will suffice to remove the ball).

The reason for the two answers: this was my thought process in action.

EDIT: Please disregard the above; both of these solutions are unstable.

In fact Scott's example is part of a general class of solutions of total length $3\pi+h+\epsilon.$ Take any two diametrically opposite points, and draw a small spherical triangle containing one of the points. Connect all six possible edges between the four points by geodesics, and finally rotate the arrangement so that one of the strings passes through the north pole.

Here is a short proof that any stable configuration must have at least four points where three or more strings meet. If there are three or less points, there is a hemisphere $H$ which contains all of the points. Take the complement $H^C$ of this hemisphere; we can remove any strings in $H^C$ because they cannot be geodesics. As $H^C$ doesn't contain the north pole, the sphere can fall out.

Note that if any strings are not geodesics between junctions, we can ignore the strings.

Here is a short proof (that is not quite rigorous) that could provide a lower bound. Suppose there is not a loop (that is, a set of points connected by geodesics) that is completely contained in the southern hemisphere. Then we may drag any points in the southern hemisphere into the northern hemisphere. (This statement is the part I can't make completely rigorous.) So the sphere must be unstable. Now if we have a loop in the southern hemisphere, there must be at least two strings meeting at the north pole, as otherwise we could simply slide all of the string off one side of the sphere.

So we must have a loop in the southern hemisphere and (not necessarily direct) connections from at least two of these points to the north pole. I can't figure out how to work a good lower bound from here.

Answer by drvitek for Product of sine

2010-10-30T05:22:55Z

From Andreescu and Andrica, Complex Numbers from A to Z p. 48.

$$\prod_{1 \le k \le n} \sin{\frac{(2k-1)\pi}{2n}} = \frac{1}{2^{n-1}}.$$

Ibid., p. 50.

"The following identities hold:

a) $$\prod_{1\le k \le n-1; \gcd{(k,n)} = 1}\sin{\frac{k\pi}{n}} = \frac{1}{2^{\phi(n)}}$$ whenever $n$ is not a power of a prime.

b) $$\prod_{1\le k \le n-1; \gcd{(k,n)} = 1}\cos{\frac{k\pi}{n}} = \frac{(-1)^{\frac{\phi(n)}{2}}}{2^{\phi(n)}}$$ for all odd positive integers $n$.

The first one completely answers your question; the next two are just for fun!

Answer by drvitek for Is there order to the number of groups of different orders?

2010-10-19T07:34:33Z

The most general statement that I have seen is due to Holder and gives the following result: if $n$ is squarefree, and if $f_p(n)$ is the number of primes $q$ with $q \mid n$ and $p \mid q-1$, then the number of groups of order $n$ is given by $$g(n) = \sum_{d\mid n}\prod_{p\mid d,\;d > 1} \frac{p^{f_p(n/d)}-1}{p-1}.$$

This formula is nic ein that it is exact; of course, the asymptotics here are very hard to extract, and given that there tend to be more groups of non-squarefree order than of squarefree order it is not terribly useful in asymptotic estimates.

Answer by drvitek for Awfully sophisticated proof for simple facts

2010-10-17T17:34:44Z

A number of high school contest problems in number theory reduce to Mihailescu's theorem. (The only perfect powers with a difference of 1 are 8 and 9.)

Answer by drvitek for Algebraic geometry

2010-10-17T07:36:00Z

Hartshorne. (It even has its own Wikipedia page!)

Answer by drvitek for On a special kind of graph connectig n point to n points.

2010-10-16T02:03:53Z

Ross's answer is more helpful in terms of structure, but I will point out that your graph is also an example of a circulant graph. Informally, a circulant graph is defined by parameters $n$ and $v$, with $v$ a vector in $\mathbb{N}^m\;(m<n)$ . One takes the empty graph on $n$ vertices labeled $1, 2, \cdots, n$, and joins vertex $i$ to vertices $i + v_1, i+v_2, \cdots, i+v_m$ (reduced modulo $n$). So for example the complete graph on three vertices has $n = 3$ and $v = (1,2)$.

Your case is the circulant graph on $2n$ vertices with vector $v = (3,5,\cdots,2n-1)$. (There are lots of other vectors $v$ which give isomorphic graphs, but this one is the easiest to see why it works.)

Answer by drvitek for Bounding the roots of the sum of two polynomials

2010-10-08T01:33:27Z

You could test if $\min{|p_1(t)|} > \max{|p_2(t)|}$ (or the reverse) over the interval $[t_{min},t_{max}]$, but this looks to be harder than computing $p_3$. This is an odd question...

Answer by drvitek for If you could redesign a high school mathematics curriculum from the ground up, what would you include?

2010-09-29T06:02:29Z

I was fortunate enough to go to a high school that had a course called Further Math (if any of you have heard of the IB curriculum, this class covered most of the topics on the IB Further Math exam) where we did basic propositional logic, Peano arithmetic, basic group theory (up to normal subgroups) and set theory up to Cantor-Schroeder-Bernstein, plus some statistics. I loved this class, although the only new thing I saw all year was CSB, and I think students might like this more than something such as calculus that they only really work with in physics class.

I would say that every high school should start students with a general logic class - introduce the mathematical formalisms (up to truth tables) and then work with real-world examples of disingenuous statements or the like. I think that students very much like learning about how adults lie to them. :P

Beyond that, as much as I hate to say it, no student should leave high school in an ideal world without knowing probability and statistics (up to the basic properties of the normal distribution). It has become such a powerful tool in our times, and yet it is so easy to lie to people with statistics: take Twain's quote, "There are three kinds of lies: lies, damned lies, and statistics."

I guess the idea here is that most high school students will be distracted enough by learning about how adults are lying to them not to notice that they're also being taught how to think critically and how to pursue truth - and that's what mathematics is really about, right?

Edit: just saw Andy's comment.

Testing permutations to see if they generate $S_n$

2010-09-12T02:26:00Z

Alright, so a similar question was recently asked about the theoretical bound for generating certain permutations in polynomial time. I had been thinking about a related problem in algorithms (with applications to a specific problem in graph theory - namely, discrete moves of sets of points among the vertices of a graph) and H A Helfgott's question inspired me to ask here.

Suppose I have some "black box" that spits out permutations $\rho_i \in S_n$. I know the following things about the permutations it spits out:

$\rho_i$ is of cycle type $(k_i,1,1,\cdots,1)$.
This "black box" is fast in $n$ (linear in $n$ or so, maybe plus a few log terms).
If I run this black box long enough, it will spit out all of the $k$-cycles in some subgroup $H \subseteq S_n$. I don't know what $H$ is a priori, although I can tell you (based on other constraints of the general problem) if $H \subseteq A_n$.

Let $G \subseteq S_n$ be the group generated by the $\rho_i$. (Note that $G$ may not in fact be either $H$ or $S_n$.)

I'd like to test if $A_n \subseteq G$.

Is there a computationally efficient test to see if the $\rho_i$ act primitively on $[1,n]$? I want to say that if they act transitively and if the $k_i$ do not all share some nontrivial factor, they act primitively, but I am not sure of this.
Assuming that the answer to (1) is yes, I can guarantee that the natural action of $G$ on $[1,n]$ is transitive and primitive. Does this guarantee that $G = A_n$? If not, what computationally non-intensive criterion do I need to add to guarantee that $G = A_n$?

Note: right now my algorithm for solving this problem is somewhere in that scary, scary territory beyond $O(n!)$ (yeah, that's how I'm testing to see if the darn thing is the alternating group), so any polynomial-time algorithm here would be super-awesome.

Answer by drvitek for Sequences of evenly-distributed points in a product of intervals

2010-09-02T16:31:26Z

One way to interpret this result is that it comes from the periodicity of the continued fraction expansion of $\phi = 1 + \frac{1}{1+\frac{1}{\cdots}}$ in the sense that it has no "better-than-expected" rational convergents, whereas for example with $\pi = (3;7,15,1,292,\cdots)$ we may stop at the 292 to get a good approximation (355/113 I believe).

So one may look at numbers of the form $x_n = (n;n,n,n,\cdots)$, which satisfy $x_n^2 -nx_n - 1 = 0$, or $$x_n = \frac{n+\sqrt{n^2+4}}{2}.$$ So a few good sequences may be for example $\left\{nx_2\right\}$ where $x_2 = 1+\sqrt{2}$, the so-called "silver ratio", or the same for $x_3 = (3+\sqrt{13})/2.$

EDIT: These are in some cases pretty good approximations; one way to measure the "well-distribution" of such a sequence is to take the fractional parts $\{\lfloor nx_n \rfloor: n = 1, \cdots, M\}$, sort them, compute the maximum difference between consecutive terms, and multiply this by $M$ to get some number in the range $[1,M)$. This can be accomplished in one line in Mathematica as follows:

WellDistribution[x_,M_]:=
Max[Differences[Sort[Table[N[FractionalPart[x*m]], {m, 1, M}]]]]*M;

Some interesting things happen with this when we vary $n$; perhaps I'll make a new post out of it.

Answer by drvitek for Asymptotic growth of a certain integer sequence

2010-08-30T00:14:40Z

This is building off of the work of Richard Borherds' answer and the comment I made there. We can provide a way to compute an upper bound which would be much better than the current exponential bound in $n$, but relies on enumerating solutions to certain Diophantine equations.

We are going to try and enumerate the distinct values of the expression $$e_11^n+e_22^n+\cdots+e_kk^n,$$ where $e_i = \pm 1$ for $i \in [1,n]$. Let $S$ be the set of all values attained by this expression. We have obviously $|S| \le 2^k$ as there are $2^k$ ways to choose the signs, but we know that two different choices for the $e_i$ may give the same numeric value. An illustrative example occurs in case $(k,n) = (5,2)$, where we have $$+1^2+2^2+3^2+4^2-5^2 = +1^2+2^2-3^2-4^2+5^2 = 5.$$ If we have two choices for the $e_i$ - for now, call the two lists of coefficients $a_i$ and $b_i$ that coincide, we may form sets $A = \{i \in [1,n]: a_i = +1, b_i = -1\}$ and $B = \{i \in [1,n]: a_i = -1, b_i = +1 \}$. Then we know that $A \cap B = \emptyset$, and more importantly, $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Now define a function $s(k,n,a,b)$, with $a \ge b$ and $a+b \le k$, to count the number of pairs of sets $(A,B)$ satisfying the following conditions:

$A \cup B \subseteq [1,k]$;
$A \cap B = \emptyset$;
$|A| = a$ and $|B| = b$;
if $a = b$, then $\max{A} < \max{B}$;
$\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Then we may write $$|S| \ge 2^k - \sum_{m=3}^k2^{k-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j).$$ Indeed, we see that if some set of choices of $e_i$ give the same numerical value, all but one will be removed by this inclusion-exclusion counting. We may simplify this a bit further by writing $$f(k,n) = \sum_{m=3}^k2^{-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j)$$ as our equation then becomes $|S| \ge 2^k(1-f(k,n))$. Now once we have established suitable bounds on $f(k,n)$, we may proceed as Richard did, noting that we simply solve for the least valid value of $k$ in the inequality $$2^k(1-f(k,n)) \ge 2\sum_{i=1}^ki^n.$$

Where does Fermat's Last Theorem come in? Well, in case $n \ge 3$, we need only sum from $m = 4$ to $k$ - there are no solutions for $m = 3$, as a solution for $m = 3$ takes the form $x^n + y^n = z^n$! So we lose what is (possibly?) the largest contributing term to $f(k)$.

EDIT: I was off by a factor of two. Darn.

Answer by drvitek for Widely accepted mathematical results that were later shown wrong?

2010-08-13T10:23:12Z

Kempe's "proof" of the four-color theorem springs to mind. Wikipedia says that Kempe published it in 1879 and it was proven to be incorrect by Heawood in 1890. As I recall, the flaw in the original argument was as follows: Kempe defined a structure on a planar graph called a Kempe chain, and argued that certain of these chains could not intersect. There was a subtle flaw in this argument (which I can't seem to find a decent explanation of) and it failed for certain large graphs - the chains can in fact intersect. Heawood provided a 25-node example of intersecting chains; the smallest counterexamples are the Fritsch and Soifer graphs on 9 nodes.

Edit: I didn't address the reknown of Kempe's proof. Wikipedia says that it was "widely acclaimed" (interesting coincidence of wording) while Thomas 1998 provides an excellent history but says little on this matter. I don't know if this could be truly considered "widely acclaimed" based on an uncited Wikipedia entry.

Answer by drvitek for Does subgroup structure of a finite group characterize isomorphism type?

2010-08-13T09:39:26Z

The modular group of order 16 and the group C8 x C2 have the same subgroup lattice. Does this provide a counterexample to what you are trying to prove?

Reference: http://www.opensourcemath.org/gap/small_groups.html

Answer by drvitek for Conjecture:It can be to Partition prime sequence to two parts of equal (or consecutive) sum

2010-08-13T09:22:45Z

Scott Carnahan had an interesting idea; let's formalize it into an actual solution. We will show that, given $n \ge 2$ a positive integer, $p_1, \cdots, p_n$ the first n primes, we have some $e_1, \cdots, e_n$ with $e_i = \pm 1$ such that $|e_1p_1 + e_2p_2 + \cdots + e_np_n| \le 1$. (Note that we may further stipulate that $e_n = 1$.) A simple parity argument from here suffices to prove the conjecture.

We will prove this by induction on $n$. The cases $2 \le n \le 6$ are trivial to verify, and were provided already by a-boy. We now fix $n \ge 7$.

We first need some asymptotics in the form of the Bertrand-Chebyshev theorem; we use the formulation that for $m > 1$ there is a prime between $m$ and $2m$.

Write $S_k = e_np_n + e_{n-1}p_{n-1} + \cdots + e_{n-k+1}p_{n-k+1}$, and let $M(k)$ be the minimum of $|S_k|$ over all tuples $(e_n, e_{n-1}, \cdots, e_{n-k+1})$. We stipulated earlier that $e_n = 1$, so we have $M(1) = p_n$. Two facts that will be useful to us in the future are that (1) $M(k+1) \le |M(k)-p_{n-k}|$ and (2) if $|a| \le |b|$, then $\min{\{|a+b|,|a-b|\}} \le |b|$.

We claim that $M(k) \le p_{n-k+1}$ for $k = 1, 2, \cdots, n-2$. We prove this by induction on $k$. The claim for $k = 1$ is trivial. Now if $M(k) \le p_{n-k}$, then we are done, as $M(k+1) \le \min{\{|M(k)+p_{n-k}|,|M(k)-p_{n-k}|\}} \le p_{n-k}$ by fact (2).

Now suppose $p_{n-k} < M(k) \le p_{n-k+1}$. Write $2m+1 = p_{n-k+1} \ge p_3 = 5$, so that $m > 1$. In this case we know that $m < p_{n-k} < M(k) \le 2m$. But then $M(k+1) \le M(k) - p_{n-k} \le 2m-(m+1) = (m-1) < p_{n-k}$ as desired.

The fact that $M(k) \le p_{n-k+1}$ is eminently useful.

Indeed, we may use it to dispatch of the even case immediately. Set $k = n-6$. Then we have $M(n-6) \le 17$. As all sums considered in $M(n-6)$ are sums of an even number of odd terms, we in fact have $M(n-6) \le 16$ and even. Now we simply note that all odd numbers between -15 and 15 are realizable as sums and differences of the first 6 primes, which is left as an easy computational exercise.

In the odd case, we consider $k = n-5$. Then $M(n-5) \le 13$. For the same parity reasons as above, we have in fact $M(n-5) \le 12$. And again, we note that all even numbers between -12 and 12 are realizable as sums and differences of the first 5 primes - another easy computational exercise.

The limits of $n-6$ and $n-5$ are the best possible for our small-case analysis.

If we were to establish an algorithm for this, we could just do the greedy algorithm on choosing $e_n$, then $e_{n-1}$, and so on, each time choosing $e_k$ so as to minimize $S_{k+1}$ (or randomly if $S_k = 0$). Our claim that $M(k) \le p_{n-k}$ will continue to be satisfied by the greedy algorithm, as the proof of the claim does not involve changing prior $e_i$. Thus our greedy-algorithm mimium modulus must satisfy the same inequality, and we continue until we are at $n-6$ or $n-5$, then finish as in our nonconstructive proof.

Answer by drvitek for Sum Equals Product

2010-08-10T17:54:18Z

Let the positive, unequal integers be $a_1 < a_2 < \cdots < a_k$ with $a_1+a_2+\cdots+a_k = a_1a_2\cdots a_k = n$. Obviously if $k = 1$ all positive integers work; suppose from now on that $k > 1$. Note that $a_k \ge k$. Then we have $a_1 + a_2 + \cdots + a_k < ka_k$, while $a_1a_2\cdots a_k \ge (k-1)!a_k$. So we must have $ka_k > (k-1)!a_k$, which means that $k > (k-1)!$. This means $k \le 3$. If $k = 2$, then we have $a_1 + a_2 = a_1a_2$, or $\frac{1}{a_1}+\frac{1}{a_2} = 1$. This can easily be seen to have only the solution $(2,2)$, which doesn't satisfy our hypothesis that the $a_i$ be unequal.

The case $k = 3$ is then the only tricky case. If $a_1 > 1$, then we have $a_1+a_2+a_3 < 3a_3$ and $a_1a_2a_3 \ge 6a_3$. So $a_1 = 1$. We then must find solutions to $1 + a_2 + a_3 = a_2a_3$. This can be rewritten as $(a_2-1)(a_3-1) = 2$, which as $a_2 < a_3$ are integers immediately gives $a_2 = 2, a_3 = 3$.

In summary, all possible solutions are $\{n\}$ for all positive integers $n$ and $\{1,2,3\}$.

History: this is definitely a classic problem; see for example 2006 USA Mathematical Olympiad problem #4 (pdf, problem is on second page), which is your problem with several restrictions removed.

Comment by drvitek

2012-02-28T17:45:39Z

As a college student and fellow RSI alum, I gotta say it does wonders for a kid who hasn't seen research mathematics up close and personal.

Comment by drvitek

2011-05-05T01:43:06Z

@Qiaochu: Your argument is nice, but irrelevant to this minimal counterexample: 271441 is 521 squared.

Comment by drvitek

2011-05-04T00:13:11Z

Indeed, there is a proof with only eleven words: rearrangement and arithmetic-geometric inequalities. (Details are left to the reader.)

Comment by drvitek

2011-05-03T15:49:06Z

Simon: try trillia.com/online-math/index.html for a modified version that somebody got.

Comment by drvitek

2011-03-30T01:09:53Z

Haha, and I just wrote that you always provide beautiful illustrations. You've done it again!

Comment by drvitek

2011-03-29T22:49:59Z

I've noticed this but haven't pointed it out; your posts have the most beautiful visuals here. Sometimes pretty pictures are quite nice!

Comment by drvitek

2011-02-08T17:15:29Z

Anna: I just saw your post as I submitted my comment. Several more things: that's a mission statement for the mathematics major, not for the department as a whole. Still, at least in reference to Duke, you may want to look at the 149S course, which is undergraduate problem-solving and has an enrollment of about 20 each year, not all of which end up being math majors. It's also taught by upperclassmen with some guidance from a professor, which is slightly unusual but works rather well.

Comment by drvitek

2011-02-08T17:10:54Z

Anna: I would be surprised if there was any high-quality research on this, simply because "problem-solving" as a general skill -- as opposed to mathematical problem-solving, which has some overlap, but is definitely distinct -- is very hard to define or measure across-the-board. You might try specific situations or something like Raven's Progressive Matrices -- which I would suspect would correlate decently with mathematical training -- but you're running into a definition problem, especially as "problem-solving" is nowadays being used as a sort of catch-all term in education-speak.

Comment by drvitek

2011-02-06T21:25:26Z

Your formula doesn't look right; all the $W_j$ are equal.

Comment by drvitek

2011-02-06T16:00:05Z

This answer is not so bad. The cyclotomic polynomial of degree 105 is the first one with a coefficient not in {-1,0,1}.

Comment by drvitek

2011-01-03T22:57:13Z

I question your choice of "intuitive" for Cantor's proof (adopting for a moment the perspective of a layperson) although beautiful is more than apt!

Comment by drvitek

2010-12-17T13:21:24Z

I think that Ax-Grothendieck can be lumped with this in a sort of "unexpected model-theoretic arguments" category.

Comment by drvitek

2010-11-01T01:55:07Z

@Ace: Thank you for taking the time to check my answer, find that it was off by one, and do the hard work in extending it! Have an upvote!

Comment by drvitek

2010-11-01T01:52:48Z

@Vagabond: Gah! A fencepost error! (To be honest, though, it was late, I knew where some semi-relevant formulas were, and I regurgitated them.)

Comment by drvitek

2010-10-30T05:39:12Z

(Edit: added solution that actually works, distinct from Scott's.)