User victor miller - MathOverflow

The Cayley Menger Theorem and integer matrices with row sum 2

2013-04-26T21:32:56Z

I just filled a gap in my education by learning about the Cayley-Menger theorem, and the Cayley-Menger determinant:

If $P_0, \dots, P_n$ are $n+1$ point in $\mathbb{R}^n$, and $d_{i,j} = |P_i - P_j|$ is the Euclidean distance from $P_i$ to $P_j$, we first form the $n+1 \times n+1$ matrix of squares of the distances (say $B$) and then form an $n+2 \times n+2$ matrix $A$ which has $B$ in the lower right hand corner, and has all the elements in the first row and column $=1$ except for the one in the upper left hand corner, which is 0.

The Cayley-Menger theorem (which is an $n$ dimensional generalization of Heron's formula for the area of a triangle) says that if $V$ is the volume of simplex whose vertices are the $P_i$, then

$(-1)^{n-1} 2^n (n!)^2 V^2 = \det(A)$.

I was interested in the structure of $\det(A)$ as a polynomial. There is a nice paper "The Cayley-Menger Determinant is Irreducible for $n \ge 3$" by Carlos d'Andrea and Martin Sombra (arXiV:math/0406359). When I calculated the number of monomials in each of the polynomials obtained by evaluating $\det(A)$, I got the sequence (starting with $n=1$):

1,1,6,22,130,822, 6202, 52552

which is sequence A002137 in the OEIS: Number of n X n symmetric matrices with positive entries, trace 0 and all row sums 2. There's no mention there of the Cayley-Menger determinant.

So the question I have, is there a one-to-one correspondence that one can find between the matrices and monomials in $\det(A)$? Even nicer, would be to find the value for the coefficient of the monomial from the matrix.

Added Later: I should have looked at the reference in the OEIS: A. C. Aitken, On the number of distinct terms in the expansion of symmetric and skew determinants, Edinburgh Math. Notes, No. 34 (1944), 1-5.

In it he gives a recurrence for the number terms in a symmetric matrix with 0's on the diagonal, and produces the same sequence. However, I still can't find a connection with the coefficients.

Binary expansion of squares

2013-04-02T16:01:29Z

I came across the following simple question: what odd integer squares have exactly 3 ones in their binary expansion?

After looking at it for a while I convinced myself that the only solutions to $r^2 = 1+ 2^m + 2^n$ (with $n > m \ge 3$) are $n=2m-2$ (the "trivial" case) and $(m,n) = (4,5),(4,9)$ (the "sporadic" cases). My first attempt was to analyze things 2-adically: write out the Taylor Series: $f(x) = 1 - 2 \sum_{n=1}^{\infty} (-1)^n C_{n-1} x^n$, where $C_n = \frac{1}{n+1} \binom{2n}{n}$ is the $n$-th Catalan number, and $v_2(x) > 0$. We have $f(x)^2 = 1 + 4x$, so that $a_m := \sqrt{1+2^m} = f(2^{m-2})$ (Note that $1+2^m$ is not a rational square when $m \ne 3$). If such an integer $r$ exists, then we must have $r \equiv \epsilon(a_m + 2^{n-1}) \bmod {2^{n+1}}$, where $\epsilon = \pm 1, \pm (1+2^n)$ is one of the 4 square roots of 1 modulo $2^{n+1}$. Also, we must have $r < 2^{(n+1)/2}$. To get rid of the annoying cases, take all of this modulo $2^{n-1}$, where we find that the top $(n-3)/2$ bits of $a_m \bmod 2^{n-1}$ must be either all 0's or all 1's. By writing out the first few terms of $f(x)$ I found that there's a run of $m-2$ 0's which corresponds to the trivial solution, and a run of $m-1$ 1's which corresponds to the sporadic solution (the condition that $m-1 \ge (n-3)/2$ limits the possible $m$'s and $n$'s to a small set). However, I don't see any easy way to show that there are no long "runs" of 1's or 0's among the higher bits of $a_m$ (by the bits, I mean to write out $a_m = \sum_{n=0}^{\infty} b_{m,n} 2^n$, where $b_{m,n} \in {0,1}$). Such a statement would be to the effect that we can't approximate $a_m$ too closely by small integers -- this is the sort of $p$-adic Diophantine approximation statement that I would think should be true, but I can't find it.

Absent that, another approach is via $S$-unit equations. This show (see below) that for each $m$, there are only a finite number $n$'s for which $1+2^m + 2^n$ is a rational square, but I'd like to prove (with the exception of the sporadic solution) that there is exactly 1. Since, as I mentioned above, $1+2^m$ is not a rational square when $m > 3$, denote by $K = K_m = \mathbb{Q}(\sqrt{1+2^m})$ . It's easy to see that the prime 2 splits in $K$: call $\frak{a},\frak{a}'$ the ideals above 2. Let $k>0$ denote the order of $\frak{a}$ in the ideal class group of $K$ and $\beta$ a generator of the principal ideal $\frak{a}^k$. Also denote conjugation of $K/\mathbb{Q}$ by $\quad '$. Then we have $r+\sqrt{1+2^m} = \epsilon \beta^t 2^u$, for some non-negative integers $t,u$ and $\epsilon \in K$ is a unit. Note that we might need to look at $r-\sqrt{1+2^m}$ instead. By taking norms we see that $2^{2n} = 2^{2u + kt}$, so that $2n = 2u+kt$. By noting that $\epsilon \beta^t 2^u - \epsilon' {\beta'}^t 2^u = 2 \sqrt{1+2^m}$, we see that $u=0,1$. For each of those values we then have an equation of the form $\alpha - \alpha' = \gamma$, where $\gamma$ is fixed, and $\alpha,\alpha'$ are $S$-units (here $S$ consists of the primes above 2), so we know that there are only a finite number of solutions. Any suggestions as to how to proceed to show that my initial guesses are correct?

Your favorite surprising connections in Mathematics

2010-02-08T00:10:18Z

There are certain things in mathematics that have caused me a pleasant surprise -- when some part of mathematics is brought to bear in a fundamental way on another, where the connection between the two is unexpected. The first example that comes to my mind is the proof by Furstenberg and Katznelson of Szemeredi's theorem on the existence of arbitrarily long arithmetic progressions in a set of integers which has positive upper Banach density, but using ergodic theory. Of course in the years since then, this idea has now become enshrined and may no longer be viewed as surprising, but it certainly was when it was first devised.

Another unexpected connection was when Kolmogorov used Shannon's notion of probabilistic entropy as an important invariant in dynamical systems.

So, what other surprising connections are there out there?

Proofs that inspire and teach

2012-04-22T18:39:51Z

I was just listening to the show "A Splendid Table" (which I'd recommend, if you're interested in food) in which they were discussing how to spot a good recipe: one which you can follow successfully and reinforces your confidence in your ability to cook. It occurred to me that since theorems/proof are like recipes (the best will prepare an intellectually tasty dish), that we could come up with an analogous checklist (with examples) for them.

Some theorems/proofs are like marvelous magic tricks which can excite and thrill you but leave you mystified as to how it's done ("How did he ever think of that?"). Others also inspire you and leave you with the feeling "I could do that". So I'd like examples of the latter. I don't have specific examples right now, but I was thinking that almost anything by Jean-Pierre Serre has that quality for me. Some might object that all of the details that I list below don't always belong in research papers, but should perhaps be relegated to text books or course notes. I'm not so sure. I've found proofs that could have been made much more accessible for me by adding only a few well-chosen remarks.

Here's what Lynne Rossetto Kasper (the host) gave

You can know ahead of time that a recipe will most likely work if you have a checklist of the key things to look for.

What key ideas, other definitions/theorems do you need to understand before launching into the proof?

One bright red flag is the extremely short recipe. It looks so easy and it can betray you in a nanosecond. That brevity often comes from cutting out the specific information you need to know to end up with something worth eating.

Some proofs are so polished and over simplified that they're like an intricate jewel box -- very pretty, but seem to be evanescent -- leave out one little piece and they fall apart.

Here's the rest of the list:

·Does the recipe tell you what you can prepare ahead?

·Does it tell you how to store the food and for how long?

I'm not sure how well this applies, but it might have to do with how to remember the theorem/proof.

·Are the ingredients specific -- not "1 pound beef," but "1 pound well-marbled beef chuck"?

·Do the instructions tell you ...
  ·What kind of pot and utensils to use?

What mathematical techniques are you using?

  ·The level of heat and/or the timing needed for each step?

I'm not so sure about this, but it might be -- into how much detail you need to go.

  ·What the food should look like, sound like, and/or smell like?

I find this quite interesting. This is a guide to tell how to know if your intuition is on the right track as you proceed.

  ·How to know if it's done?

A lot of times this is obvious, but there are a lot of proofs, at whose end, I'm forced to sit and think as to why it's finished!

  ·How to serve?

How to talk/write about this theorem/proof.

Answer by Victor Miller for FFTs over finite fields?

2010-10-01T12:43:54Z

There are a few different approaches to this:

1) As Peter Shor mentioned you can use a $3^n$ point transform with Bluestein's algorithm.

2) Even though there are no $2^n$ roots of unity there are substitutes for them (first implicitly discussed by Leonard Carlitz, and then explicitly by David Cantor). Look here for a good account of this http://www.math.clemson.edu/~sgao/papers/GM10.pdf

This algorithm is most likely the most efficient one in practice.

3) There's an observation of Shmuel Winograd who noticed that, using the relation between multiplicative and additive characters you can convert an FFT on $N$ points to the calculation of a cyclic convolution on $N-1$ points. And $N-1$ might factor nicely.

Answer by Victor Miller for Ways to prove the fundamental theorem of algebra

2012-04-15T02:59:11Z

I'm surprised that no-one's mentioned the proof using Roueche's theorem:

Given $f,g$ holomorphic and $C$ a closed contour if $|g(z)|< |f(z)|$ on $C$ then $f$ and $f+g$ have the same number of zeros (counting multiplicity) in the interior of $C$. There's an easy proof of this using the Cauchy integral formula.

If Let $g(z) = a_{n-1} z^{n-1} + \cdots + a_0$, and $f(z) = z^n$. If $R$ is sufficiently big then $|g(z)|<|f(z)|$ on the circle of radius $R$ with the center at 0. Thus $p(z) := z^n + g(z)$ has $n$ zeros inside that circle.

[As a side note, when I was taught this by Lipman Bers, he picturesquely referred to it as the "dog on the leash theorem" -- it's essentially a winding number argument]

Complexity of Labeled Graph Homomorphism

2012-04-05T16:58:38Z

The following recreational math problem has been floating around work:

We're given an $m \times n$ grid ($m,n$ positive integers). We wish to label the elements of the grid with letters so that we can spell out the name of the nine (this originated before Pluto was demoted) planets, where allowable neighbors of a point in the grid are those points on the grid which are immediately up, down, left or right (provided they exist). The challenge was to find the grid of the smallest area ($mn$) which allowed such a labeling. The best answer given was for a $4 \times 8$ grid. Since it's clear that if an $m \times n$ grid is possible then so is an $(m+1) \times n$ and $m \times (n+1)$ grid, we're really interested in finding those pairs $(m,n)$ which are maximally impossible. It appears that this is the set $\{ (5,6), (6,5), (4,7),(7,4) \}$ , but both of these impossibility results come from a very long running backtrack program. It would be nicer if there was a better proof.

So, stepping back from the specific problem we see that it's an instance of the following problem:

We're given $G, H$ undirected graphs, with the vertices of $G$ labeled: $l(v)$ is the label of $v \in V(G)$. We wish to find a homomorphism $f :G \rightarrow H$ (i.e. a map from $f: V(G) \rightarrow V(H)$ such that if $(v,v') \in E(G)$ then $(f(v),f(v')) \in E(H)$) and a labeling $l$ of vertices of $H$ such that $l(f(v)) = l(v)$ for all $v \in V(G)$. In our original problem, $G$ is the disjoint union of 9 paths, labeled with the spelling of planets' names, and $H$ is the $m \times n$ grid graph. I've found that there has been some work on the homomorphism existence problem for graphs, which is a generalization of graph coloring (take $H=K_n$ the complete graph on $n$ vertices. Existence of a homomorphism $f : G \rightarrow H$ is the same as an $n$-coloring of $G$). But there is a dichotomy: if $H$ is bipartite, then this is easy (since it becomes the same as determining whether or not $G$ is bipartite), and if not, it's NP-complete. The graphs in the above problem are both bipartite, but the labeling requirement appears to make it much more difficult. So, does anyone know about the generalization that I've given which requires a certain labeling?

Answer by Victor Miller for Solubility of the quintic?

2012-04-09T16:09:59Z

Dave Dummit's paper "Solving Solvable Quintics" http://www.ams.org/journals/mcom/1991-57-195/S0025-5718-1991-1079014-X/S0025-5718-1991-1079014-X.pdf constructs a sextic out of the coefficients of the quintic which has a rational root if and only if the quintic has a solvable Galois Group. Although this is stated over $\mathbb{Q}$ I believe that it applies over any field of characteristic 0 or > 5.

Answer by Victor Miller for How do I iterate over binary trees?

2012-04-05T19:58:02Z

The paper "Binary Tree Gray Codes" by Proskurowski and Ruskey, in the Journal of Algorithms http://dx.doi.org/10.1016/0196-6774(85)90040-9 gives a method of generating all binary trees, so that the successive in the generation differ by a constant amount. It also gives references to previous such algorithms.

Answer by Victor Miller for Fastest Algorithm to Compute the Sum of Primes?

2012-03-29T16:06:15Z

I'll put in a plug for my original paper with Lagarias and Odlyzko, as well as a recent paper by Bach, Klyve and Sorenson: http://www.ams.org/journals/mcom/2009-78-268/S0025-5718-09-02249-2/home.html Computing prime harmonic sums Math. Comp. 78 (2009), 2283-2305. Although the algorithms of Lagarias and Odlyzko (with the extra algorithm of Odlyzko-Schonhage for computing good approximations to a bunch of values of $\zeta(s)$) are asymptotically the best, having complexity $O(x^{1/2 + \epsilon})$ the combinatorial algorithms will probably work best for any reasonable ranges. Though one should look at J. Buethe, J. Franke, A. Jost, and T. Kleinjung, "Conditional Calculation of pi(10^24)", Posting to the Number Theory Mailing List, Jul 29 2010. A little more detail (that's all I have right now) is contained in the talk of David Platt: www.maths.bris.ac.uk/~madjp/junior%20talk.pdf . The idea in the combinatorial method is the following:

Suppose that $f(n)$ is a completely multiplicative function of the positive integers. In the case of calculating $\pi(x)$, we take $f(n) = 1$. In the case of calculating the sum of the primes $\le x$ we take $f(n) = n$. In the case of Calculating $\pi(x,a,q)$ we take $f(n)$ to be a Dirichlet character mod $q$.

Define $\phi(x,a)$ as the sum of $f(n)$ for all integers $n \le x$ which are not divisible by the first $a$ primes. Clearly $\phi(x,0) = \sum_{n \le x} f(n)$. We have the recursion:

$\phi(x,a+1) = \phi(x,a) - f(p_{a+1})\phi(x/p_{a+1},a).$

Imagine that you have a labeled tree, where the labels are $\pm f(k) \phi(x/k,b)$ for some $k$ and $b$. You can expand any node in the tree you want by applying the above formula. This has the property that it leaves the sum of the values at the leaves the same. So the idea is to start with a tree consisting of one node labeled $\phi(x,\pi(\sqrt x))$ and keep expanding until either $b=0$ or $x/k < $ some cutoff. If you accumulate all such nodes you can evaluate all of them by sieving (and a special data structure -- see the Lagarias-Miller-Odlyzko paper for details), and the optimal value for the cutoff is $x^{2/3}$ perhaps multiplied by some logarithmic factors.

Here's the reference to my paper with Lagarias and Odlyzko: Computing $\pi(x)$: The Meissel-Lehmer Method Author(s): J. C. Lagarias, V. S. Miller, A. M. Odlyzko Source: Mathematics of Computation, Vol. 44, No. 170 (Apr., 1985), pp. 537-560

Simple proofs for the existence of elliptic curves having a given number of points

2012-02-08T18:23:23Z

Yesterday, after he gave a nice talk, Dick Gross and I were chatting and he brought up the following annoying problem: suppose that for $p$ a prime that $H_p$ is the "Hasse interval" $[p - 2 \sqrt{p},p+2\sqrt{p}]$. Then, for every point $r \in H_p$ there is an elliptic curve $E_{a,b}: y^2 = x^3 + a x + b$ over $\mathbb{F}_p$ such that $N_p(E_{a,b}) = r$, where $N_p(C)$ denotes the number of projective points of the curve $C$. But the only proof that we knew of this fact involved the whole theory of complex multiplication and Deuring's theorems about reduction. So the question arose if there is a simpler proof of this fact, say by using $p$-adic methods. I even asked for the weaker case: let $H_p' = [p+\sqrt{p},p+2\sqrt{p}]$. Can you prove the existence of an $E_{a,b}$ with $N_p(E_{a,b}) \in H_p'$ with a fairly simple proof?

On the converse side, there's Hasse's proof of the Riemann Hypothesis for elliptic curves over finite fields, that $N_p(E_{a,b}) \in H_p$, which does involve a fair amount of machinery (even though it's been simplified). Suppose that we're after the weaker statement:

There are absolute constants $0 < c_1 < c_2$ such that if $y^2 = x^3 + a x + b$ is an elliptic curve over $\mathbb{Q}$ then, for sufficiently large primes $p$

$c_1 p \le N_p(E_{a,b}) \le c_2 p$.

More generally, if $f(x,y) \in \mathbb{Q}[x,y]$ is an absolutely irreducible polynomial of total degree $d$ that there are $0 < c_1 < c_2$ only depending on $d$ such that

$ c_1 p \le N_p(f) \le c_2 p$ for all sufficiently large primes $p$.

Again, how simple a proof is there for this statement?

When $f(x,y) = a x^2 + b y^2 + c$ which is genus 0, the simplest proof I know of consists in showing

1) If there is a point $P$ in $\mathbb{F}_p^2$ on $f$, then one can explicitly construct a one-to-one correspondence between the projective points on $f$ and the projective line, by using the pencil of lines through $P$.

2) Use the pigeon hole principle to show the existence of a point on $f$:

If $a \ne 0$ there are exactly $(p+1)/2$ values of $a x^2$, so we can see that the intersection $\{ax^2\} \cap \{-(c + by^2)\}$ has at least one point (we just barely made it).

I know of no such simple proof for an elliptic curve $E$.

Answer by Victor Miller for Which mathematicians have influenced you the most?

2011-09-02T18:01:44Z

Who: G. H. Hardy

When: As a high school student

Where: The book "Pure Mathematics" -- from which I learned real analysis.

Who: Serge Lang

When: As a college student

Where: At Columbia, Serge Lang was my mathematical mentor. I took Math I C/II C from him (which I'd describe as freshman mathematics for prospective Ph.D.'s -- it was pretty much an undergraduate Abstract Algebra, plus Real Analysis plus more in two semesters). His energy and love of mathematics was inspiring. I know that nobody who met him felt neutral about him. He was incredibly dedicated to his students. If he liked you he would move mountains.

Who: Lipman Bers

When: As a college student

Where: At Columbia, Lipman Bers was my other inspiration. I took Math III C/IV C from him -- sophomore mathematics for prospective Ph.D.'s. Besides being a very lucid lecturer, with fantastic geometric intuition, he was sophisticated and kind -- a prince among men! By example he showed how one could live a mathematical life (at perhaps a bit less than the frenetic pace of Serge Lang).

A search for optimal order ideals

2011-08-11T18:47:41Z

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in name for a partial order.

Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers $\mathbb{N}$. As I mentioned in my other question, $M$ has a partial order defined as follows: If $S \in M$ and $i \ge 1$ is an integer, denote by $S_i$ the $i$-th largest element of $S$. We say that $S \ge_R T$ if $|S| \ge |T|$ and $S_i \ge T_i$ for $i = 1, \dots, |T|$. For any finite subset $A \subset M$ define the polynomial $$ f_A(t) := \sum_{S \in A} \sum_{T \in A} t^{|S \Delta T|},$$

where $S \Delta T$ denotes the symmetric difference. If $ p \in (0,1)$ say that a finite subset $A \subset M$ is optimal at $p$ if $f_A(p) \ge f_B(p)$ for all subsets $B \subset M$ with $|B| = |A|$. Say that $A$ is optimal, if there is some $p \in (0,1)$ for which $A$ is optimal at $p$. Say that $A$ is isomorphic to $B$ if there is a permutation $\pi \in S_{\infty}$ (permutations of $\mathbb{N}$ which only move a finite set of elements) and a subset $T \in M$ such that $B = \{ \pi(S) \Delta T : S \in A \}$. It's easy to see that if $A$ is isomorphic to $B$ then $f_A(t) = f_B(t)$.

Another way of thinking of $M$ is to consider it to be infinite sequences of 0's and 1's with only a finite number of 1's (i.e. infinite bit-strings). Then cardinality becomes Hamming weight and symmetric difference becomes exclusive or. Isomorphic sets of bit-strings would be obtained from one another by permuting coordinates (every bit string in the set gets permuted in the same way), and then xoring everything with a common bit-string.

In (Gordon, Miller, Ostapenko) we proved that if $A$ is optimal then it is isomorphic to an order ideal for the order $\le_R$. For a fixed value $N$ for $|A|$ we were then able to make a search for all order ideals of size $N$, and then determine the optimal ones (for some $p$) among those. We were able to do this by looking at the subposet of $M$ of elements $S \in M$ such that $|\{ T : T \le_R S \}| \le N$. In particular we were interested in optimal sets whose cardinality is a power of 2. The search for cardinality 64 took about 1/2 hour. Unless we have a new idea the search for $N=128$ is out of the question. For $N=64$ there are 4384627 order ideals of cardinality 64, but less than 100 of them are optimal. Thus I was hoping that if there are theorems around about the structure of the order ideals of $M(\infty)$ that that might help us to make a more efficient search. In the previous question, Richard Stanley pointed out that the partial order that I was using had been studied before in one of his papers .

The name for a partial order

2011-08-06T19:24:35Z

In a recent paper of mine, my co-authors found that a partial order that we were using was contained in a paper by Kundgen. In it, he called it "right-shifted partial order". I was curious, and found that I couldn't find that term used anywhere other than in our paper and Kundgen's. It wasn't even in the Handbook of Combinatorics in the chapter on set systems. I wrote to Kundgen and asked where he got that terminology from. He told me that he had heard it in a seminar conducted by Doug West. I wrote to West, and he said that he had never heard of it! I have a sneaking suspicion that it's been used before but under a different name, and so would like to know what that name is.

Here is a description of the partial order:

The set over which we define the partial order is the set of finite subsets of $\mathbb{N}$ the positive integers. If $S$ is a finite subset of $\mathbb{N}$ denote by $S_i$ the $i$-th largest element of $S$. Say that $S \ge_R T$ if $|S| \ge |T|$ and $S_i \ge T_i$ for $i=1, \dots, |T|$. This is a refinement of the partial order given by set inclusion. The name "right-shifted" comes from the fact that if you make the standard identification of $S$ with the vector $(v_i)$ where $v_i = 1$ if $i \in S$ and $0$ otherwise and write this bit string big-endian then to get the elements which are $\le_R$ a particular bit vector we can shift any 1 "to the right" (including deleting it entirely).

For reference, here's a link to Kundgen's paper: http://www.csusm.edu/akundgen/papers/isoperi.ps

Here's a link to our paper that uses it: http://arxiv.org/abs/0806.3284

The number of orbits of a permutation action

2011-07-20T14:09:09Z

Let $G$ be a finite group acting on a finite set $\Omega$. A general question is to determine the sequence $o_k(\Omega)$, where $o_k(\Omega)$ is the number of orbits on $G$ for the natural action of $G$ on the set of $k$-subsets of $\Omega$. It's well-known that if $G=S_n$ and the action on $\Omega =[n] := \{1, \ldots, n \}$ is the standard permutation action, that $o_k(\Omega) = 1$ (i.e. since $S_n$ is $n$-fold transitive the induced action on $k$-sets is transitive). I'm interested in being able to figure out the sequence $o_k(\Omega_r)$ where $G=S_n$, but where $\Omega$ is the set of all $r$-subsets of $[n]$, say for $r=2$ or $3$. I had hesitated asking this question since I thought that the answer must be well-known, but after a little while looking around I haven't been able to find it.

What I have been able to figure out is the following: if $A$ is a set of $r$-subsets of $[n]$ I'll define its signature: Let $U$ denote the multiset which is the multiset union of the elements of $A$ -- i.e. the multiplicity of an element $x \in U$ is the number of elements of $A$ which contain $x$. The signature of $A$ is the multiset of multiplicities in $U$. Then the action of $S_n$ is transitive on sets of a fixed signature. So the answer to my question is to count the number of possible signatures.

[Addition: if $s$ is the signature of a set $A$ of $k$-subsets of the set of $r$-subsets of $[n]$, then the sum of the elements (with multiplicity) of $s$ is $r k$. Thus a signature is a partition of of $rk$ into $\le n$ parts. However, it's not clear to me that all such partitions actually occur as signatures]

A ring of invariants in characteristic 2

2010-03-20T16:58:23Z

Let $K$ be an algebraic closure of $\mathbb{F}_2$ . The cyclic group $C_{2^n}$ acts on $K[x_0, \dots, x_{2^n-1}]$ by cyclically permuting the $x_i$: $a : x_i \rightarrow x_{i + a \bmod 2^n}$ . Is there a nice description of the ring of invariants of $C_{2^n}$ acting this way on $K[x]$? Things are quite easy when the characteristic $ \ne 2$, but look quite a bit more intricate here since, e.g. the group ring $K[C_{2^n}]$ is not semi-simple.

A polytope associated with the Hadamard Transform

2011-07-18T16:13:58Z

In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in http://arxiv.org/abs/0911.1388 , the following polyhedron arises:

The variables $x_i$ are indexed by $i \in M_n$. The inequalities are

$ x_i \ge 0$ for all $i \in M_n$.

$\sum_{i \in M_n} \chi(i) x_i \ge 0$ for all additive characters $\chi: M_n \rightarrow \pm 1$.

This comes up when $f_A: M_n \rightarrow \{0,1\}$ is the characteristic function of a subset $A$ of $M_n$ (in this case the putative complement $A$ which is the set of elements for which would translate $V$ to create a partition of $M_n$). Then $x_i =f_A \ast f_A(i)$ gives an element of the above polyhedron. This polyhedron is homogeneous, so it is convenient to add the additional constraints to make it a polytope:

$x_0 = a$ for some $a >0 $ and $\sum_{i \in M_n} x_i = b$ for some $b>0$.

In the case that the $x_i$ come from a function like the $f_A$ above (associated with a subset $A$) we have $a = |A|$ and $b = |A|^2$. I'm wondering if there's a nice description of this polytope -- for example a description of its vertices/faces, etc. Has anybody looked at this before?

There are a lot of symmetries of this polytope. The group $\text{GL}_n(\mathbb{F}_2)$ operates it via $x_i \rightarrow x_{i \cdot g}$.

Answer by Victor Miller for System of Diophantine equations

2011-07-14T04:52:51Z

Thanks to Noam Elkies for telling me to post my one-liner to solve this in gp (this dates from around 1993):

fermat(p) = qflll([lift(sqrt(Mod(-1,p))),p;1,0])[1,]

What this does is to use the well known construction (I think that it's in Hardy and Wright), that says that if $0 < a < (p-1)/2$ satisfies $a^2 = -1 \bmod{p}$ if you run the continued fraction algorithm for $a/p$ "half-way" to get the convergent $r/s$ then $r^2 + s^2 = p$. What the above one-liner does is to set up the lattice $$\pmatrix {a&p \cr 1 & 0 \cr}$$ The shortest vector in this lattice has $L^2$ norm of $p$.

Relations in matrix semigroups

2010-02-03T22:02:27Z

Suppose that $A_1, \dots, A_k \in M_n(\mathbb{Q})$ and $S$ is the semigroup generated by them. Two questions: are there always a finite set of relations ${R_i}$ among the $A_j$ such that $S$ is isomorphic to semigroup $\langle a_1, \dots, a_k | R_i\rangle$? By a relation I mean something of the form $w = w'$ where $w,w'$ are two words. If this is true, is it true that there is a bound on the length of the relations? That is, is there an $l$ which is a function of $n$, and perhaps the maximum absolute values of the entries of the $A_i$ so that we may always find a set of relations $R_i$ of length $\le l$?

The complexity of the leading fractional bit of a power of a rational number

2011-04-24T19:05:38Z

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are fixed (think of $p/q = 3/2$) and $n$ varies. There were a number of suggestions, but all of them clearly had complexity proportional to $n$. So my question is, for concreteness, let $b(n) = \lfloor 2(3/2)^n \rfloor \bmod 2$ (the leading fractional bit of $(3/2)^n$). Suppose that $n$ is specified in binary. What is the complexity (both time and space) of calculating the function $b(n)$? After thinking about it for a while I wouldn't be surprised if it's exp-space hard. Does anyone know anything about this?

Answer by Victor Miller for Efficient computation of the least fraction with square denominator greater than the square root of 2.

2011-06-08T03:23:06Z

You should try the algorithms in Elkies' paper (from 2000) "Rational points near curves ..." http://arxiv.org/abs/math/0005139 . His idea is to cover the curve with a bunch of small rectangles, and use lattice basis reduction within each such region. He proves a result which either says that there are small number of solutions or all the solutions lie on a line.

Historical question about modularity of CM curves

2011-06-01T19:57:32Z

I'm looking for the answer of who first proved modularity of CM curves? That is if $E$ is an elliptic curve over $\mathbb{Q}$ which has complex multiplication then there's a non-constant morphism from $X_0(N)$ to $E$ for some $N$ (not necessarily the conductor). The possible names that I've thought of are Hecke, Deuring, Weil or Shimura. Does anybody know something more definite?

How do the number of plane curves over a finite field of a fixed genus increase with the degree?

2011-05-18T22:11:32Z

Let $k$ be a finite field. We define $N(d,g)$ to be the number of plane curves $f(x,y)$ defined over $k$ of degree $d$ with (geometric) genus $g$. If $D(d) := (d-1)(d-2)/2$ (the maximum possible genus), I would expect that as $d$ goes to infinity that the proportion of curves of degree $d$ with genus $D(d)$ would go to 1. If, on the other hand, we're interested in curves of a fixed small genus (say $g=0$ or 1), I would expect that $N(d,g)$ would still approach infinity, albeit at a much slower rate. The question that I have is how do $N(d,0)$ or $N(d,1)$ approach infinity? Is it a polynomial in $\log d$, faster, slower?

I realize that there has been a lot done with enumerative geometry (Gromon-Witten, Caporaso-Harris), but that seems a bit different, since it always works over an algebraically closed field, and classifies curves by having them pass through some set of generic points, and possibly prescribing, tangency, etc.

Answer by Victor Miller for How "often" does LLL-reduction produce "optimal" result ? Is there condition (or informal understanding) on lattice that it LLL is optimal ?

2011-04-16T20:23:05Z

This paper

"On the reduction of a random basis" by Ali Akhavi,Jean-Francois Marckert, and Alain Rouault

http://www.siam.org/proceedings/analco/2007/anl07_028aakhavi.pdf

purports to answer your question.

Added later: There is a real question about what is the right meaning of a "random lattice". You should see the paper "On the equidistribution of Hecke points" by Daniel Goldstein and Andrew Mayer Forum Mathematicorum Volume 15, Issue 2, Pages 165–189. In that paper they look at the natural Haar measure on the space of $n$-dimensional lattices.

Historical Articles about zeta functions of curves

2011-03-12T15:39:18Z

Are there any historical articles about the origins of zeta functions of curves over global fields (undoubtedly starting with $\mathbb{Q}$)? In particular who (and when did this happen) first have the idea of creating such a thing? Was it by analogy with the zeta functions of number fields?

Answer by Victor Miller for What is the shortest Ph.D. thesis?

2011-02-08T16:18:09Z

Barry Mazur's thesis on the proof of the Schoenflies conjecture (and introducing the method of infinite repetition in topology) is 5 pages long.

Answer by Victor Miller for Examples of two different descriptions of a set that are not obviously equivalent?

2011-01-23T13:20:28Z

You could discuss Beatty sequences. If $r>1$ is an irrational real define $\mathcal{B}_r =\{ \lfloor r \rfloor, \lfloor 2 r \rfloor, \dots\}$ a subset of the positive integers. The complement of $\mathcal{B}_r$ in the positive integers is $\mathcal{B}_s$, where $\frac{1}{r} + \frac{1}{s} = 1$. See, for example, http://en.wikipedia.org/wiki/Beatty_sequence

Answer by Victor Miller for A question about primes as an additive basis

2011-01-19T16:23:06Z

You should look at Andrew Granville's survey http://www.dms.umontreal.ca/~andrew/PDF/GoldbachFinal.pdf . Among other things he talks about the behavior of $r_2(N)$ (or a suitably weighted version of it -- giving the representation $p+q=N$ the weight $\log p \log q$) on the average: if one looks at the average error between that and the conjectured Hardy-Littlewood "main term" one can show that this is small on the RH. This would indicate that finding large deviations from the main term would be quite hard.

Finch's sequence over $\mathbb{F}_3$

2010-12-29T21:31:31Z

In http://algo.inria.fr/csolve/seqmod3.pdf -- "Periodicity in sequences mod 3" Steven Finch (also cited in Sloane's OEIS A112683) defines the following sequences in $\mathbb{F}_3$:

For each positive integer $k$, consider the sequence $x_n$ in $\mathbb{F}_3$

$x_i = 0$ for $i=1,2, \dots, k-1$, $x_k = 1$ and

$x_n = x_{n-1} + x_{n-k}^2$ for $n > k$.

Since we're working in a finite field, the sequence is eventually periodic. Let $N(k)$ denote the period. Can we write down a formula for $N(k)$? Can we give good bounds, etc? The values which have been computed are:

1,4,4,9,19,4,4,22,36,4,4,45,64,4,4,102,1082,231,4,188,272,4,412,225,202,4,4

Richard Pinch had an explanation for all the 4's as follows:

"The semi-ubiquitous 4's come from the fact that 2011 is a cycle when $k$ is $2 \bmod 4$ and 2201 when $k$ is $3 \bmod 4$. Of course the sequence does not have to lock on to that cycle: for example when $k$ is 18 or 23".

I can't find any more references to the problem than the ones that I give.

Answer by Victor Miller for Proofs that require fundamentally new ways of thinking

2010-12-12T17:59:28Z

The Ax-Kochen theorem about zeros of forms over the $p$-adics which was proved using model theory.

Comment by Victor Miller

2013-04-26T22:25:57Z

@Gunter: not all the coefficients are positive, so that we need to add a sign to $2^k$ -- is it the sign of the permutation?

Comment by Victor Miller

2013-04-26T22:23:04Z

@Gunter: thank you for a clear a lucid explanation.

Comment by Victor Miller

2013-04-26T21:53:37Z

@Gunter, I wondered the same. They must mean non-negative. I'll point this out to NJA Sloane.

Comment by Victor Miller

2013-04-03T13:34:01Z

@Mike, You're welcome. I just finished looking at your paper in more detail. Your 3-adic argument for the corresponding base 3 problem is similar to the 2-adic argument that I gave above (though the 2-adic case is a bit simpler since you only have 0/1 coefficients). All I was missing (which is what I alluded to at the end of the paragraph) is the Pade approximation to $\sqrt{1+x}$ that you got from Beukers.

Comment by Victor Miller

2013-04-03T01:46:17Z

@Mike: I can see why you were familiar with Szalay's paper. You were being too modest not mentioning your preprint: math.ubc.ca/~bennett/Be-Selfridge.pdf

Comment by Victor Miller

2013-04-03T01:39:07Z

@Mike: Thanks for the reference. Here's a link to the paper titanic.nyme.hu/~laszalay/publications/TIJNEW.pdf . The heavy lifting was done by Beukers, who showed that there are only at most 4 solutions to $x^2 - D = 2^n$ (variables, $x$ and $n$)

Comment by Victor Miller

2012-06-12T14:13:17Z

@David: I haven't looked at Ken's result in quite a while, so I don't recall the conditions that he put on it. I'll try to find it today. In addition I think that the result is only valid for new cusp forms.

Comment by Victor Miller

2012-06-12T03:52:56Z

@David: I only proved it for level 1. Ken Ribet later proved it in general. I'll try to dig up the refernce,

Comment by Victor Miller

2012-06-10T16:13:08Z

@David, This was something that I proved in chapter 2 of my thesis. Basically, the proof is what Francois gave in his answer. Higher level is more subtle, but is true for modular forms for $\Gamma_0(\ell)$, proved by Ribet and Hida.

Comment by Victor Miller

2012-05-10T02:10:27Z

This thesis, by M.A. Simachew, www.algant.eu/documents/theses/simachew.pdf has a comprehensive survey of what was known in 2009.

Comment by Victor Miller

2012-04-22T21:35:00Z

@Martin: If you'll point these out to me, I'll gladly withdraw it. I understand your point about blog posts, but having examples of such proofs is really important.

Comment by Victor Miller

2012-04-22T20:44:10Z

@Mrc Plm: I said "So I'd like examples of the latter." It wasn't phrased as a question. I should have hilighted it.

Comment by Victor Miller

2012-04-16T22:34:39Z

@Gerhard: You're right. It looks like (3,11) is also a maximal impossible.

Comment by Victor Miller

2012-04-15T02:39:59Z

I learned this proof from Serge Lang in 1965 when I was a freshman in college. He attributed it to Emil Artin (and he was the keeper of the Artin flame, so I'd definitely believe it).

Comment by Victor Miller

2012-04-12T16:54:00Z

Thanks, I agree that it looks close.