User alon amit - MathOverflow

Answer by Alon Amit for Useful tricks in experimental mathematics

2013-05-06T05:48:27Z

For the first question ("is there a nice book/article..."), I think the answer ie Yes: Sanjoy Mahajan's Street-Fighting Mathematics, which also exists in a free CC version, summarizes a good number of useful tricks and meta-tricks, some well-known, some less so.

Answer by Alon Amit for What's the "best" proof of quadratic reciprocity?

2009-10-20T17:14:28Z

I don't think anyone mentioned Eisenstein's classic proof. This presentation of it is pretty good. I find it clear and attractive, especially because it sort of avoids Gauss' Lemma (which is a clever gadget but somehow off-putting).

Answer by Alon Amit for Combinatorial results without known combinatorial proofs

2009-11-14T07:28:03Z

Warning: this used to be a great example, but I'm afraid it no longer is.

Let $H(n)$ be the number of horizontally-convex polyominoes in the plane, where "horizontally convex" means just what you think it means, and equivalence is just up to translations (so mirror images and rotations are considered distinct). Using a sequence of manipulations with two-variable generating functions and an amazing amount of cancellation, one finds that

$H(n) = 5H(n-1) - 7H(n-2) + 4H(n-3)$.

I learned this from Gil Kalai in 1991 (and the result is much older), and I'm quite sure there was no known combinatorial proof of this surprising result for a while. However fairly recently Dean Hickerson found one. I'm sure Dean thought that this looks frustratingly like something that ought to have a combinatorial proof, and then he proceeded to resolve this frustration in the only possible way.

Answer by Alon Amit for Proofs without words

2009-12-14T07:53:45Z

The cover of Peter Winkler's first book is a great proof without words of a statement which I'll leave you to guess, regarding the combinatorics of tiling a heaxagon with rhombi.

EDIT: I think the guessing game isn't helpful. The statement is that when tiling a perfect hexagon with the appropriate kind of rhombi of various orientations, the number of tiles in each orientation is the same. The image is slightly misleading in its use of color; there ought to be just three colors, corresponding to the three orientations.

Answer by Alon Amit for out-trees and least upper boundness

2011-09-15T09:05:00Z

Perhaps I'm misunderstanding the definitions, but it seems like any lattice (in the poset sense) naturally defines a digraph which satisfies LUB but is, in most cases, not an out-tree. The simplest example is the digraph consisting of 4 vertices $A, B_1, B_2, C$ with edges from $A$ to each $B_i$ and from each $B_i$ to $C$. This has the LUB property far as I can tell, and the underlying graph is not a tree.

Answer by Alon Amit for Do good math jokes exist?

2009-10-18T23:47:24Z

Tom Lehrer was a Mathematician and this comes through in several of his famous skits. Not precisely a "math joke", but still mathy and pretty darn funny.

Maximal ideals in the ring of continuous real-valued functions on R

2009-11-02T23:52:29Z

For a compact space $K$, the maximal ideals in the ring $C(K)$ of continuous real-valued functions on $K$ are easily identified with the points of $K$ (a point defines the maximal ideal of functions vanishing at that point).

Now take $K=\mathbb{R}$. Is there a useful characterization of the set of maximal ideals of $C(\mathbb{R})$, the ring of continuous functions on $\mathbb{R}$? Note that I'm not imposing any boundedness conditions at infinity (if one does, I think the answer has to do with the Stone-Čech compactification of $\mathbb{R}$ - but I can't say I'm totally clear on that part either). Is this ring too large to allow a reasonable description of its maximal ideals?

Answer by Alon Amit for Examples of theorems misapplied to non-mathematical contexts

2011-06-01T06:46:27Z

A rare instance of Gödel-abuse in a published paper is "Bacterial wisdom, Gödel's theorem and creative genomic webs" by Eshel Ben-Jacob. Here, Gödel's theorem is used to prove that "a system cannot self-design another system which is more advanced than itself", with application to genomics.

Answer by Alon Amit for Examples of theorems misapplied to non-mathematical contexts

2011-06-01T06:31:51Z

I submit, to your consideration, this paper by Frank Tipler, Professor at Tulane University. The paper was published in the peer-reviewed Reports on Progress in Physics, volume 68 (2005), pages 897-964. Tipler's book "The Physics of Christianity" is based on this paper.

Tipler invokes Gödel's theorem (see p. 905 onwards), Presburger arithmetic, Löwenheim-Skolem, Hales' proof of the Kepler conjecture (the latter only as an example, I believe), and various other mathematical results.

Proof of no rational point on Selmer's Curve 3x^3+4y^3+5z^3=0

2009-10-27T05:40:48Z

The projective curve $3x^3+4y^3+5z^3=0$ is often cited as an example (given by Selmer) of a failure of the Hasse Principle: the equation has solutions in any completion of the rationals $\mathbb Q$, but not in $\mathbb Q$ itself.

I don't think I've ever seen a proof of the latter claim — is someone able to provide an outline? What are the necessary tools?

Answer by Alon Amit for About an exercise in Serre's "Trees"

2011-01-11T00:32:20Z

I don't have the book next to me but I'm quite sure I remember the exercise and, as far as I was able to determine, your first guess is the correct one. This isn't an amalgam exercise in any natural way (or any way at all), but rather an example to put the case of 4 generators in perspective.

Answer by Alon Amit for Most memorable titles

2010-11-01T06:15:46Z

"Holey Sheets" - Pfaffians and Subdeterminants as D-brane Operators in Large N Gauge Theories.

What (if anything) happened to Intersection Homology?

2009-11-26T06:04:41Z

In the early 1990's, Gil Kalai introduced me to a very interesting generalization of homology theory called intersection homology, which existed for like 10 years back then I believe. Defined initially by Goresky and MacPherson, this is a version of homology which agrees with ordinary homology on manifolds, but also retains crucial properties like Poincare Duality and Hodge Theory on singular (non-)manifolds. The original definition was combinatorial, but it was later re-interpreted in sheaf-theoretic terms (perverse sheaves?).

Back then it certainly looked like an exciting new development. So, I'm curious - where does the field stand today? Is it still thriving, or has it been merged with something else, or just faded away?

Answer by Alon Amit for roots of permutations

2010-10-12T04:06:40Z

Two your last question - "how far may it be generalized" - Richard Stanley answered when you fix the equation ($X^2=c$) and vary the group. You may also wonder about other equations. The situation is interesting: There are equations and groups with the property that the identity is not the RHS yielding the most solutions. This is so even though the LHS has no constants, just variables.

One may rephrase the question as follows: given a word $w=w(X_1,X_2,\ldots,X_r)$ in the free group $F_r$ with variables $X_1,\ldots,X_r$, and given any finite group $G$, one may naturally consider $w$ as inducing a function $G^r \to G$ by plugging elements of $G$ as variables. This in turn defines a probability distribution on $G$: if you plug uniform random elements, what do you get? The most likely outcome is often, but not always, the identity.

In fact, the probability of getting the identity can be made arbitrarily small iff the group is non-solvable. I circulated this as a conjecture some years ago and it was proven by Miklos Abert (for the non-solvable case) and Nikolov and Segal (for the solvable one).

Answer by Alon Amit for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T05:54:48Z

I sometimes mention the efficient generation of expander graphs. In layspeak, an expander graph is "a network where every node is connected to say only 5 other nodes, but you have to cut a million such connections in order to separate two substantial portions of the network from each other". It is possible to generate large expander graphs explicitly, but this is very far from trivial (see Lubotzky, Phillips and Sarnak); on the other hand, in an appropriate sense, a random large network is amazingly good.

(how do you make a random network with 5 neighbors per node? start by imagining that each node is made up of 5 pebbles, pair up the pebbles randomly, and merge the pebbles into nodes).

This is an algorithm-to-generate, not an algorithm-to-decide, but this shouldn't cause too much trouble with most layfolks.

Answer by Alon Amit for Does the "continuous locus" of a function have any nice properties?

2009-10-07T18:03:29Z

Yes, here's a quick proof that any given $G_\delta$ (in $\mathbb{R}$) can be realized as the set of continuity points of some real-valued function.

Let $G$ be a given $G_\delta$ set in $\mathbb{R}$, meaning $G = \cap_{i=1}^\infty G_i$, each $G_i$ an open set. Define a function $f:\mathbb{R} \to \mathbb{R}$ as follows: $f(x)=0$ if $x$ is in $G$. If x is not in $G$, there is some $k$ such that $x$ is not in $G_k$; let $k$ be minimal with that property. Define $f(x)=1/k$ if $x$ is rational and $f(x)=-1/k$ if $x$ is irrational.

If I'm not very much mistaken, $G$ is precisely the set of continuity points of this $f$. I'm happy to leave this as an exercise for now :-) Let me know if you're not sure how to do it, or - worse - if I'm just wrong about the construction.

If 2^x and 3^x are integers, must x be as well?

2010-03-09T01:21:45Z

I'm fascinated by this open problem (if it is indeed still that) and every few years I try to check up on its status. Some background: Let $x$ be a positive real number.

If $n^x$ is an integer for every $n \in \mathbb{N}$ then $x$ must be an integer. This is a fun little puzzle.
If $2^x$, $3^x$ and $5^x$ are integers then $x$ must be an integer. This requires fairly sophisticated tools, and can be derived from the results in e.g. Lang, Algebraic values of meromorphic functions. II., Topology 5, 1966.
Finally, if all you know is that $2^x$ and $3^x$ are integers, then as far as I know it is not known if $x$ is forced to be an integer (unbelievable, isn't it?). Although of course one can never be certain, I am quite sure this was still the case as recently as 2003.

So the question is, is that still an open problem, and is there any sort of relevant progress that may provide some hope?

Answer by Alon Amit for Problem suggestions for polymath for undergraduates research

2010-07-09T09:06:00Z

Pick any of the problems in the archives of Al Zimmermann's Programming Contests, and make progress either on the theoretic side (tighter upper bounds / lower bounds / asymptotics) or the computational side.

A specific nice example could be Point Packing.

Answer by Alon Amit for Pseudo-random number generation algorithms

2010-06-26T06:40:46Z

Don't miss this wonderful post by Marsaglia. He's not a fan of the Mersenne Twister and offers some strong PRNGs with exceptionally small code footprints. One of his examples is:

static unsigned long 
x=123456789,y=362436069,z=521288629,w=88675123,v=886756453; 
      /* replace defaults with five random seed values in calling program */ 
unsigned long xorshift(void) 
{unsigned long t; 
 t=(x^(x>>7)); x=y; y=z; z=w; w=v; 
 v=(v^(v<<6))^(t^(t<<13)); return (y+y+1)*v;}

Answer by Alon Amit for Proofs without words

2009-12-14T08:05:58Z

In an attempt to push the bar towards the non-trivial, I'll mention the proof that the boundary complex of every polytope is shellable. The proof is virtually word-free but requires an actual movie rather than a still image: imagine yourself in a spaceship, taking off in a straight line from one of the facets, away from the polytope. Every once in a while a new facet is visible to you; under assumptions of general position, this provides a shelling of the complex (obviously, you need to fly off to projective infinity and come back on the other side).

This was assumed by Euler but first proved only in 1970 by Brugesser and Mani, who said that the idea came to him in a dream. More details here (search for "shellability") or here.

Answer by Alon Amit for Connectedness of random distance graph on integers

2010-04-21T18:55:15Z

Well, as it stands isn't the answer No? Just take $p(n) = 1$ if $n$ is even and $0$ if $n$ is odd. The graph will have at least two components consisting of the even and odd integers.

EDIT: retracted. Sorry. This is not (and cannot be made) decreasing. Missed that requirement.

Answer by Alon Amit for Open source mathematical software.

2010-03-22T18:50:30Z

GAP is fantastic for group theory, combinatorics and and number theory. Sage is becoming very popular and essentially includes GAP as well.

Answer by Alon Amit for What are the worst notations, in your opinion ?

2010-03-18T23:58:51Z

My candidate would be the (internal) direct sum of subspaces $U \oplus V$ in linear algebra. As an operator it is equivalent to sum but with the side effect of implying that $U \cap V = \lbrace 0\rbrace$. Whenever I had a chance to teach linear algebra I found this terribly confusing for students.

Answer by Alon Amit for A historical question: Hurwitz, Luroth, Clebsch, and the connectedness of M_g

2010-03-10T08:10:11Z

Does this help a little?

"In a 1891 paper, Hurwitz explains how the set of degree d simple covers (all ﬁbers consist of at least d-1 points) P1 (the projective line – Riemann sphere) has a structure of complex manifold. In this he follows a much earlier (1867) paper of Clebsch who showed the connectedness of the space of simple covers. Hurwitz's paper thereby applies to show the connectedness of the moduli space of compact surfaces of genus g."

If nothing else this may point you to folks who may know (Pierre Debes and Mike Fried).

Answer by Alon Amit for Teaching Methods and Evaluating them

2010-03-06T16:58:51Z

You may find it interesting to observe how Eric Mazur, professor at Physics at Harvard, determined that his own teaching methods were inadequate. The whole talk is fascinating in its description of an alternative teaching approach he has developed; However to your question I think the important point is the method used by Mazur to initially observe that something is not going well at all.

Starting at 00:04:00, Prof. Mazur describes the initial criteria which led him to believe he was doing a good job (success at the end of term questionnaire). Then - more importantly - starting at 00:06:30, he describes how a survey of conceptual understanding helped him realize that something was very fundamentally wrong. The specific proposal is running an identical pre-course and post-course test which attempts to examine the quality of basic understanding of the concepts.

Answer by Alon Amit for How should I approximate real numbers by algebraic ones?

2009-10-27T18:39:52Z

Basically you're looking for a small integral relation among the powers of the given number. This can be done effectively with the LLL algorithm (Lenstra-Lenstra-Lovasz) and variations of it (especially PSLQ), and indeed this approach is used to determine "inverse symbolic" candidates for an approximate real number. Look up papers by Plouffe and Bailey such as this one.

Answer by Alon Amit for Checking if two graphs have the same universal cover

2010-02-09T09:29:51Z

Two finite graphs have the same universal cover iff they have a common finite cover. This surprising fact was first proved by Tom Leighton here:

Frank Thomson Leighton, Finite common coverings of graphs. 231-238 1982 33 J. Comb. Theory, Ser. B

I'm quite sure the paper also presents an algorithm for determining if this is the case for two given graphs; essentially you develop a refined "degree" sequence for the graphs, starting from "# of vertices of degree k" and refining to "# of vertices of degree k with so-and-so vertices of degree l" etc.

As an aside, the reason this result is so surprising is that it says something highly non-trivial about groups acting on trees (any two subgroups of Aut(T) with a finite quotient are commensurable, up to conjugation), and proving this result directly via group-theoretic methods is surprisingly difficult (and interesting). There's a paper of Bass and Kulkarni which pretty much does just that.

Edit: I just ran a quick search and found this sweet overview: "On Leighton's Graph Covering Theorem".

A parametrization of Heronian triangles

2009-12-29T16:10:58Z

Let $a,b,c$ be integers which are the sides of a triangle with integral area, a so called Heronian triangle. This website attributes to Gauss the result that there must then exist integers $m,n,p,q$ such that

$a = mn(p^2+q^2)$

$b = (mp)^2+(nq)^2$

$c = (m+n)(mp^2-nq^2)$

(where I left out a $4pq$ factor designed to make the radius of the circumscribed circle integral as well). It's not hard to see that the triangle defined by these formulas is indeed Heronian, however I could neither prove nor find a reference for the fact that this parametrization is exhaustive.

Can someone do one of these two things?

Thanks!

(Note: I'm communicating this question on behalf of my dad, who is really the person who looked into that but is not easily capable of asking it himself over here. I may be slow to respond on his behalf if questions come up).

Two finite groups with the same identical relations?

2009-10-15T18:34:31Z

An identical relation on a group G is a word w in Fr, the free group on r elements (for some r), such that evaluating w on any r-tuple of elements of G yields the identity (this just means substituting elements of g for the variables in w, and evaluating the product).

Does the complete set of identical relations characterize a finite group? That is, are there two finite groups with precisely the same set of identical relations?

Answer by Alon Amit for Is there a "finitary" solution to the Basel problem?

2009-12-21T18:49:16Z

I think that the 14th and last proof in Robin Chapman's collection is just that. It relies on the formula for the number of representations of an integer as a sum of four squares, which is kind of overkill, but anyway.

Comment by Alon Amit

2011-09-19T16:22:51Z

I'm still very confused. Yes, lattices contain semicycles, that's just the point - you were asking if every LUB graph is a (kind of) tree, and it isn't. You now changed the question to ask if every connected digraph without semicycles (which further satisfies LUB) must be a (kind of) tree. Well, it is, by definition, right? The underlying undirected graph certainly is a tree (connected and cycle free). This is just an out-tree except that we haven't chosen a specific root.

Comment by Alon Amit

2011-09-16T06:17:18Z

Is it known that this can't occur with the alternating groups? Empirically it looks like the sizes of the conjugacy classes of $A_n$ all have at least 3 prime factors once $n>8$.

Comment by Alon Amit

2011-09-16T01:57:23Z

What do "clip" and "half edges" mean?

Comment by Alon Amit

2011-09-12T07:29:02Z

This isn't the right level of question of this site, I'm afraid. You should try math.stackexchange.com. (see the FAQ here: mathoverflow.net/faq)

Comment by Alon Amit

2011-09-11T22:20:12Z

Shouldn't you be looking at the Laplacian, rather than the adjacency matrix? For non-regular graphs I'm not sure if the second largest eigenvalue is the thing that controls mixing. Also, the operation you're interested in seems more like taking the cone over $G$, rather than a suspension.

Comment by Alon Amit

2011-08-05T22:29:45Z

An awesome summary!

Comment by Alon Amit

2011-07-28T05:34:22Z

I'm curious: what is "Pollack's new book"?

Comment by Alon Amit

2011-06-18T06:59:52Z

Sorry if that's a silly question but in example 1), a particle starting at (0,1) won't go anywhere unless you give it some initial horizontal velocity. Are you suggesting that the separation point tends to the indicated point as that velocity tends to 0?

Comment by Alon Amit

2011-06-17T07:09:26Z

I don't understand your modified question. Of course every problem in NP can be reduced some subset of NP problems - it can be "reduced" to itself, and often to lots of other problems polynomially-equivalent to it. Why does that imply that NPC is empty?

Comment by Alon Amit

2011-06-11T06:50:36Z

In line 3, did you mean "the sequence whose $n$-th term is..."?

Comment by Alon Amit

2011-06-03T03:50:42Z

If he does, it's a slam dunk.

Comment by Alon Amit

2011-06-01T07:58:16Z

The proof you linked to seems perfectly constructive to me. It presents a simple algorithm for finding a vertex connected to all vertices in U and not connected to any vertex in V given any pair (U,V), and from this the explicit construction of an isomorphic copy of any finite graph.

Comment by Alon Amit

2011-04-18T23:26:54Z

@Ho Chung Siu, do you happen to have a copy of that paper anywhere accessible?

Comment by Alon Amit

2011-04-14T02:45:09Z

This is totally tangential but I just want to say I strongly disagree with the sentiment of the first sentence. If statements and proofs were typically "in the same world", math would be so dull. Dystopia.

Comment by Alon Amit

2011-04-10T04:12:24Z

I changed the question's title to better correspond to its content. You don't appear to be interested in the historical development of the theorem, but rather the motivation behind this characterization. Perhaps a better way to phrase the question would be to ask, is there any algorithmic or theoretical advantage to this (rather daunting) condition.