User victor miller - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T17:50:02Z http://mathoverflow.net/feeds/user/2784 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/128864/the-cayley-menger-theorem-and-integer-matrices-with-row-sum-2 The Cayley Menger Theorem and integer matrices with row sum 2 Victor Miller 2013-04-26T21:32:56Z 2013-04-28T22:50:23Z <p>I just filled a gap in my education by learning about the Cayley-Menger theorem, and the Cayley-Menger determinant:</p> <p>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.</p> <p>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</p> <p>$(-1)^{n-1} 2^n (n!)^2 V^2 = \det(A)$.</p> <p>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$):</p> <p>1,1,6,22,130,822, 6202, 52552</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/126284/binary-expansion-of-squares Binary expansion of squares Victor Miller 2013-04-02T16:01:29Z 2013-04-02T22:01:15Z <p>I came across the following simple question: what odd integer squares have exactly 3 ones in their binary expansion?</p> <p>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 &lt; 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.</p> <p>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 <code>$K = K_m = \mathbb{Q}(\sqrt{1+2^m})$</code>. 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 <code>$K/\mathbb{Q}$</code> 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?</p> http://mathoverflow.net/questions/14574/your-favorite-surprising-connections-in-mathematics Your favorite surprising connections in Mathematics Victor Miller 2010-02-08T00:10:18Z 2012-12-31T00:26:13Z <p>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.</p> <p>Another unexpected connection was when Kolmogorov used Shannon's notion of probabilistic entropy as an important invariant in dynamical systems.</p> <p>So, what other surprising connections are there out there?</p> http://mathoverflow.net/questions/94867/proofs-that-inspire-and-teach Proofs that inspire and teach Victor Miller 2012-04-22T18:39:51Z 2012-12-30T07:18:24Z <p>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.</p> <p>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.</p> <p>Here's what <a href="http://www.publicradio.org/columns/splendid-table/features/how_to_spot_good_recipes_a_checklist.html" rel="nofollow"> Lynne Rossetto Kasper </a> (the host) gave</p> <blockquote> <p>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.</p> </blockquote> <p>What key ideas, other definitions/theorems do you need to understand before launching into the proof?</p> <blockquote> <p>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.</p> </blockquote> <p>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.</p> <blockquote> <p>Here's the rest of the list:</p> <p>·Does the recipe tell you what you can prepare ahead?</p> <p>·Does it tell you how to store the food and for how long?</p> </blockquote> <p>I'm not sure how well this applies, but it might have to do with how to remember the theorem/proof.</p> <blockquote> <p>·Are the ingredients specific -- not "1 pound beef," but "1 pound well-marbled beef chuck"?</p> <p>·Do the instructions tell you ...</p> <pre><code> ·What kind of pot and utensils to use? </code></pre> </blockquote> <p>What mathematical techniques are you using?</p> <blockquote> <pre><code> ·The level of heat and/or the timing needed for each step? </code></pre> </blockquote> <p>I'm not so sure about this, but it might be -- into how much detail you need to go.</p> <blockquote> <pre><code> ·What the food should look like, sound like, and/or smell like? </code></pre> </blockquote> <p>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.</p> <blockquote> <pre><code> ·How to know if it's done? </code></pre> </blockquote> <p>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!</p> <blockquote> <pre><code> ·How to serve? </code></pre> </blockquote> <p>How to talk/write about this theorem/proof.</p> http://mathoverflow.net/questions/40485/ffts-over-finite-fields/40741#40741 Answer by Victor Miller for FFTs over finite fields? Victor Miller 2010-10-01T12:43:54Z 2012-10-15T22:51:23Z <p>There are a few different approaches to this:</p> <p>1) As Peter Shor mentioned you can use a $3^n$ point transform with Bluestein's algorithm.</p> <p>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 <a href="http://www.math.clemson.edu/~sgao/papers/GM10.pdf" rel="nofollow">http://www.math.clemson.edu/~sgao/papers/GM10.pdf</a></p> <p>This algorithm is most likely the most efficient one in practice.</p> <p>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.</p> http://mathoverflow.net/questions/10535/ways-to-prove-the-fundamental-theorem-of-algebra/94087#94087 Answer by Victor Miller for Ways to prove the fundamental theorem of algebra Victor Miller 2012-04-15T02:59:11Z 2012-04-15T03:22:00Z <p>I'm surprised that no-one's mentioned the proof using Roueche's theorem:</p> <p>Given $f,g$ holomorphic and $C$ a closed contour if $|g(z)|&lt; |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.</p> <p>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)|&lt;|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.</p> <p>[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]</p> http://mathoverflow.net/questions/93231/complexity-of-labeled-graph-homomorphism Complexity of Labeled Graph Homomorphism Victor Miller 2012-04-05T16:58:38Z 2012-04-11T12:45:17Z <p>The following recreational math problem has been floating around work:</p> <p>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 <code>$\{ (5,6), (6,5), (4,7),(7,4) \}$</code>, but both of these impossibility results come from a <em>very</em> long running backtrack program. It would be nicer if there was a better proof.</p> <p>So, stepping back from the specific problem we see that it's an instance of the following problem:</p> <p>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?</p> http://mathoverflow.net/questions/93553/solubility-of-the-quintic/93581#93581 Answer by Victor Miller for Solubility of the quintic? Victor Miller 2012-04-09T16:09:59Z 2012-04-09T16:09:59Z <p>Dave Dummit's paper "Solving Solvable Quintics" <a href="http://www.ams.org/journals/mcom/1991-57-195/S0025-5718-1991-1079014-X/S0025-5718-1991-1079014-X.pdf" rel="nofollow">http://www.ams.org/journals/mcom/1991-57-195/S0025-5718-1991-1079014-X/S0025-5718-1991-1079014-X.pdf</a> 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.</p> http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees/93249#93249 Answer by Victor Miller for How do I iterate over binary trees? Victor Miller 2012-04-05T19:58:02Z 2012-04-05T19:58:02Z <p>The paper "Binary Tree Gray Codes" by Proskurowski and Ruskey, in the Journal of Algorithms <a href="http://dx.doi.org/10.1016/0196-6774(85)90040-9" rel="nofollow">http://dx.doi.org/10.1016/0196-6774(85)90040-9</a> 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.</p> http://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/92581#92581 Answer by Victor Miller for Fastest Algorithm to Compute the Sum of Primes? Victor Miller 2012-03-29T16:06:15Z 2012-03-30T04:07:59Z <p>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: <a href="http://www.ams.org/journals/mcom/2009-78-268/S0025-5718-09-02249-2/home.html" rel="nofollow">http://www.ams.org/journals/mcom/2009-78-268/S0025-5718-09-02249-2/home.html</a> 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:</p> <p>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$.</p> <p>Define $\phi(x,a)$ as the sum of $f(n)$ for all integers $n \le x$ which are <em>not</em> divisible by the first $a$ primes. Clearly $\phi(x,0) = \sum_{n \le x} f(n)$. We have the recursion:</p> <p>$\phi(x,a+1) = \phi(x,a) - f(p_{a+1})\phi(x/p_{a+1},a).$</p> <p>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 &lt;$ 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.</p> <p>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</p> http://mathoverflow.net/questions/87916/simple-proofs-for-the-existence-of-elliptic-curves-having-a-given-number-of-point Simple proofs for the existence of elliptic curves having a given number of points Victor Miller 2012-02-08T18:23:23Z 2012-02-09T00:57:50Z <p>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?</p> <p>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:</p> <p>There are absolute constants $0 &lt; c_1 &lt; 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$</p> <p>$c_1 p \le N_p(E_{a,b}) \le c_2 p$.</p> <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 &lt; c_1 &lt; c_2$ only depending on $d$ such that</p> <p>$c_1 p \le N_p(f) \le c_2 p$ for all sufficiently large primes $p$.</p> <p>Again, how simple a proof is there for this statement?</p> <p>When $f(x,y) = a x^2 + b y^2 + c$ which is genus 0, the simplest proof I know of consists in showing</p> <p>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$.</p> <p>2) Use the pigeon hole principle to show the existence of a point on $f$:</p> <p>If $a \ne 0$ there are exactly $(p+1)/2$ values of $a x^2$, so we can see that the intersection <code>$\{ax^2\} \cap \{-(c + by^2)\}$</code> has at least one point (we just barely made it).</p> <p>I know of no such simple proof for an elliptic curve $E$.</p> http://mathoverflow.net/questions/5499/which-mathematicians-have-influenced-you-the-most/74382#74382 Answer by Victor Miller for Which mathematicians have influenced you the most? Victor Miller 2011-09-02T18:01:44Z 2011-09-02T18:01:44Z <p>Who: G. H. Hardy</p> <p>When: As a high school student</p> <p>Where: The book "Pure Mathematics" -- from which I learned real analysis.</p> <p>Who: Serge Lang</p> <p>When: As a college student</p> <p>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.</p> <p>Who: Lipman Bers</p> <p>When: As a college student</p> <p>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).</p> http://mathoverflow.net/questions/72709/a-search-for-optimal-order-ideals A search for optimal order ideals Victor Miller 2011-08-11T18:47:41Z 2011-08-11T19:22:56Z <p>At the behest of Gerhard Paseman I'll describe the problem that I alluded to in <a href="http://mathoverflow.net/questions/72260/the-name-for-a-partial-order" rel="nofollow"><em>name for a partial order</em></a>.</p> <p>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|},$$</p> <p>where $S \Delta T$ denotes the symmetric difference. If $p \in (0,1)$ say that a finite subset $A \subset M$ is <em>optimal at $p$</em> if $f_A(p) \ge f_B(p)$ for all subsets $B \subset M$ with $|B| = |A|$. Say that $A$ is <em>optimal</em>, 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)$.</p> <p>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.</p> <p>In <a href="http://arxiv.org/pdf/0806.3284v2" rel="nofollow"> (Gordon, Miller, Ostapenko) </a> 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 <a href="http://math.mit.edu/~rstan/pubs/pubfiles/84.pdf" rel="nofollow"> one of his papers </a>.</p> http://mathoverflow.net/questions/72260/the-name-for-a-partial-order The name for a partial order Victor Miller 2011-08-06T19:24:35Z 2011-08-06T19:52:17Z <p>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.</p> <p>Here is a description of the partial order:</p> <p>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).</p> <p>For reference, here's a link to Kundgen's paper: <a href="http://www.csusm.edu/akundgen/papers/isoperi.ps" rel="nofollow">http://www.csusm.edu/akundgen/papers/isoperi.ps</a></p> <p>Here's a link to our paper that uses it: <a href="http://arxiv.org/abs/0806.3284" rel="nofollow">http://arxiv.org/abs/0806.3284</a></p> http://mathoverflow.net/questions/70813/the-number-of-orbits-of-a-permutation-action The number of orbits of a permutation action Victor Miller 2011-07-20T14:09:09Z 2011-08-03T07:20:54Z <p>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.</p> <p>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 <em>signature</em>: Let $U$ denote the <em>multiset</em> 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.</p> <p>[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]</p> http://mathoverflow.net/questions/18860/a-ring-of-invariants-in-characteristic-2 A ring of invariants in characteristic 2 Victor Miller 2010-03-20T16:58:23Z 2011-07-24T23:13:40Z <p>Let $K$ be an algebraic closure of <code>$\mathbb{F}_2$</code>. The cyclic group $C_{2^n}$ acts on <code>$K[x_0, \dots, x_{2^n-1}]$</code> by cyclically permuting the $x_i$: <code>$a : x_i \rightarrow x_{i + a \bmod 2^n}$</code>. 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.</p> http://mathoverflow.net/questions/70637/a-polytope-associated-with-the-hadamard-transform A polytope associated with the Hadamard Transform Victor Miller 2011-07-18T16:13:58Z 2011-07-19T03:36:11Z <p>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 <a href="http://arxiv.org/abs/0911.1388" rel="nofollow">http://arxiv.org/abs/0911.1388</a> , the following polyhedron arises:</p> <p>The variables $x_i$ are indexed by $i \in M_n$. The inequalities are</p> <p>$x_i \ge 0$ for all $i \in M_n$.</p> <p>$\sum_{i \in M_n} \chi(i) x_i \ge 0$ for all additive characters $\chi: M_n \rightarrow \pm 1$.</p> <p>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:</p> <p>$x_0 = a$ for some $a >0$ and $\sum_{i \in M_n} x_i = b$ for some $b>0$.</p> <p>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?</p> <p>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}$.</p> http://mathoverflow.net/questions/70208/system-of-diophantine-equations/70295#70295 Answer by Victor Miller for System of Diophantine equations Victor Miller 2011-07-14T04:52:51Z 2011-07-14T05:26:11Z <p>Thanks to Noam Elkies for telling me to post my one-liner to solve this in gp (this dates from around 1993):</p> <p>fermat(p) = qflll([lift(sqrt(Mod(-1,p))),p;1,0])[1,]</p> <p>What this does is to use the well known construction (I think that it's in Hardy and Wright), that says that if $0 &lt; a &lt; (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&amp;p \cr 1 &amp; 0 \cr}$$ The shortest vector in this lattice has $L^2$ norm of $p$.</p> http://mathoverflow.net/questions/14061/relations-in-matrix-semigroups Relations in matrix semigroups Victor Miller 2010-02-03T22:02:27Z 2011-07-10T16:22:05Z <p>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$?</p> http://mathoverflow.net/questions/62854/the-complexity-of-the-leading-fractional-bit-of-a-power-of-a-rational-number The complexity of the leading fractional bit of a power of a rational number Victor Miller 2011-04-24T19:05:38Z 2011-07-06T13:52:20Z <p>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?</p> http://mathoverflow.net/questions/65223/efficient-computation-of-the-least-fraction-with-square-denominator-greater-than/67203#67203 Answer by Victor Miller for Efficient computation of the least fraction with square denominator greater than the square root of 2. Victor Miller 2011-06-08T03:23:06Z 2011-06-08T03:23:06Z <p>You should try the algorithms in Elkies' paper (from 2000) "Rational points near curves ..." <a href="http://arxiv.org/abs/math/0005139" rel="nofollow">http://arxiv.org/abs/math/0005139</a> . 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.</p> http://mathoverflow.net/questions/66685/historical-question-about-modularity-of-cm-curves Historical question about modularity of CM curves Victor Miller 2011-06-01T19:57:32Z 2011-06-01T22:37:32Z <p>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?</p> http://mathoverflow.net/questions/65376/how-do-the-number-of-plane-curves-over-a-finite-field-of-a-fixed-genus-increase-w How do the number of plane curves over a finite field of a fixed genus increase with the degree? Victor Miller 2011-05-18T22:11:32Z 2011-05-19T01:41:43Z <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/61945/how-often-does-lll-reduction-produce-optimal-result-is-there-condition-or/61951#61951 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 ? Victor Miller 2011-04-16T20:23:05Z 2011-04-16T20:40:37Z <p>This paper</p> <p>"On the reduction of a random basis" by Ali Akhavi,Jean-Francois Marckert, and Alain Rouault</p> <p><a href="http://www.siam.org/proceedings/analco/2007/anl07_028aakhavi.pdf" rel="nofollow">http://www.siam.org/proceedings/analco/2007/anl07_028aakhavi.pdf</a></p> <p>purports to answer your question.</p> <p>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.</p> http://mathoverflow.net/questions/58270/historical-articles-about-zeta-functions-of-curves Historical Articles about zeta functions of curves Victor Miller 2011-03-12T15:39:18Z 2011-03-13T09:19:51Z <p>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?</p> http://mathoverflow.net/questions/54775/what-is-the-shortest-ph-d-thesis/54785#54785 Answer by Victor Miller for What is the shortest Ph.D. thesis? Victor Miller 2011-02-08T16:18:09Z 2011-02-08T16:18:09Z <p>Barry Mazur's thesis on the proof of the Schoenflies conjecture (and introducing the method of infinite repetition in topology) is 5 pages long.</p> http://mathoverflow.net/questions/52899/examples-of-two-different-descriptions-of-a-set-that-are-not-obviously-equivalent/52949#52949 Answer by Victor Miller for Examples of two different descriptions of a set that are not obviously equivalent? Victor Miller 2011-01-23T13:20:28Z 2011-01-24T18:41:07Z <p>You could discuss <em>Beatty sequences</em>. 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, <a href="http://en.wikipedia.org/wiki/Beatty_sequence" rel="nofollow">http://en.wikipedia.org/wiki/Beatty_sequence</a></p> http://mathoverflow.net/questions/52467/a-question-about-primes-as-an-additive-basis/52528#52528 Answer by Victor Miller for A question about primes as an additive basis Victor Miller 2011-01-19T16:23:06Z 2011-01-19T16:23:06Z <p>You should look at Andrew Granville's survey <a href="http://www.dms.umontreal.ca/~andrew/PDF/GoldbachFinal.pdf" rel="nofollow">http://www.dms.umontreal.ca/~andrew/PDF/GoldbachFinal.pdf</a> . 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.</p> http://mathoverflow.net/questions/50678/finchs-sequence-over-mathbbf-3 Finch's sequence over $\mathbb{F}_3$ Victor Miller 2010-12-29T21:31:31Z 2010-12-29T21:31:31Z <p>In <a href="http://algo.inria.fr/csolve/seqmod3.pdf" rel="nofollow">http://algo.inria.fr/csolve/seqmod3.pdf</a> -- "Periodicity in sequences mod 3" Steven Finch (also cited in Sloane's OEIS A112683) defines the following sequences in $\mathbb{F}_3$:</p> <p>For each positive integer $k$, consider the sequence $x_n$ in $\mathbb{F}_3$</p> <p>$x_i = 0$ for $i=1,2, \dots, k-1$, $x_k = 1$ and</p> <p>$x_n = x_{n-1} + x_{n-k}^2$ for $n > k$.</p> <p>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:</p> <p>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</p> <p>Richard Pinch had an explanation for all the 4's as follows:</p> <p>"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".</p> <p>I can't find any more references to the problem than the ones that I give.</p> http://mathoverflow.net/questions/48771/proofs-that-require-fundamentally-new-ways-of-thinking/49152#49152 Answer by Victor Miller for Proofs that require fundamentally new ways of thinking Victor Miller 2010-12-12T17:59:28Z 2010-12-12T17:59:28Z <p>The Ax-Kochen theorem about zeros of forms over the $p$-adics which was proved using model theory.</p> http://mathoverflow.net/questions/128864/the-cayley-menger-theorem-and-integer-matrices-with-row-sum-2/128867#128867 Comment by Victor Miller Victor Miller 2013-04-26T22:25:57Z 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? http://mathoverflow.net/questions/128864/the-cayley-menger-theorem-and-integer-matrices-with-row-sum-2/128867#128867 Comment by Victor Miller Victor Miller 2013-04-26T22:23:04Z 2013-04-26T22:23:04Z @Gunter: thank you for a clear a lucid explanation. http://mathoverflow.net/questions/128864/the-cayley-menger-theorem-and-integer-matrices-with-row-sum-2 Comment by Victor Miller Victor Miller 2013-04-26T21:53:37Z 2013-04-26T21:53:37Z @Gunter, I wondered the same. They must mean non-negative. I'll point this out to NJA Sloane. http://mathoverflow.net/questions/126284/binary-expansion-of-squares/126319#126319 Comment by Victor Miller Victor Miller 2013-04-03T13:34:01Z 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. http://mathoverflow.net/questions/126284/binary-expansion-of-squares/126319#126319 Comment by Victor Miller Victor Miller 2013-04-03T01:46:17Z 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: <a href="http://www.math.ubc.ca/~bennett/Be-Selfridge.pdf" rel="nofollow">math.ubc.ca/~bennett/Be-Selfridge.pdf</a> http://mathoverflow.net/questions/126284/binary-expansion-of-squares/126319#126319 Comment by Victor Miller Victor Miller 2013-04-03T01:39:07Z 2013-04-03T01:39:07Z @Mike: Thanks for the reference. Here's a link to the paper <a href="http://titanic.nyme.hu/~laszalay/publications/TIJNEW.pdf" rel="nofollow">titanic.nyme.hu/~laszalay/publications/TIJNEW.pdf</a> . 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$) http://mathoverflow.net/questions/42809/how-many-hecke-operators-span-the-level-1-hecke-algebra Comment by Victor Miller Victor Miller 2012-06-12T14:13:17Z 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. http://mathoverflow.net/questions/42809/how-many-hecke-operators-span-the-level-1-hecke-algebra Comment by Victor Miller Victor Miller 2012-06-12T03:52:56Z 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, http://mathoverflow.net/questions/42809/how-many-hecke-operators-span-the-level-1-hecke-algebra Comment by Victor Miller Victor Miller 2012-06-10T16:13:08Z 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. http://mathoverflow.net/questions/96518/is-mathbbz2-cos-frac-pik-a-euclidean-domain Comment by Victor Miller Victor Miller 2012-05-10T02:10:27Z 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. http://mathoverflow.net/questions/94867/proofs-that-inspire-and-teach Comment by Victor Miller Victor Miller 2012-04-22T21:35:00Z 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. http://mathoverflow.net/questions/94867/proofs-that-inspire-and-teach Comment by Victor Miller Victor Miller 2012-04-22T20:44:10Z 2012-04-22T20:44:10Z @Mrc Plm: I said &quot;So I'd like examples of the latter.&quot; It wasn't phrased as a question. I should have hilighted it. http://mathoverflow.net/questions/93231/complexity-of-labeled-graph-homomorphism Comment by Victor Miller Victor Miller 2012-04-16T22:34:39Z 2012-04-16T22:34:39Z @Gerhard: You're right. It looks like (3,11) is also a maximal impossible. http://mathoverflow.net/questions/10535/ways-to-prove-the-fundamental-theorem-of-algebra/10626#10626 Comment by Victor Miller Victor Miller 2012-04-15T02:39:59Z 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). http://mathoverflow.net/questions/93231/complexity-of-labeled-graph-homomorphism/93763#93763 Comment by Victor Miller Victor Miller 2012-04-12T16:54:00Z 2012-04-12T16:54:00Z Thanks, I agree that it looks close.