User gene s. kopp - MathOverflow

Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable?

2012-07-16T20:21:25Z

One might say, "a random subset of $\mathbb{R}$ is not Lebesgue measurable" without really thinking about it. But if we unpack the standard definitions of all those terms (and work in ZFC), it's not so clear.

Let $\Sigma \subset 2^\mathbb{R}$ be the sigma-algebra of all Lebesgue measurable sets. Give $2^\mathbb{R}$ the product measure. (It's a product of continuum many copies of the two-point set.) We want to say that $\Sigma$ is a null set in $2^\mathbb{R}$...but is $\Sigma$ even measurable?

Laci Babai posed this question casually several years ago, and no one present knew how to go about it, but it might be easy for a set theorist.

Also, a related question: Think of $2^\mathbb{R}$ as a vector space over the field with two elements and $\Sigma$ as a subspace. (Addition is xor, that is, symmetric set difference.) What is $\dim\left(2^\mathbb{R}/\Sigma\right)$?

It's not hard to see that $\dim\left(2^\mathbb{R}/\Sigma\right)$ is at least countable, so if $\Sigma$ were measurable, it would be a null set. But that's as far as I made it.

What is Ricardo Pérez-Marco's eñe product? Does it explain his statistical results on differences of zeta zeros?

2011-12-09T03:53:54Z

The number theory community here at University of Michigan is abuzz with talk of this paper recently posted to the arxiv. If you haven't seen it already, the punch line is that the global differences of imaginary parts of zeta zeros show an unusual tendency not to be close to imaginary parts of zeta zeros. "Riemann zeros repel their deltas."

The people I have talked to have said that this simple observation appears to be completely new and potentially groundbreaking. Here are my questions:

1) Has anyone independently verified these statistics? (See my histograms below, and also the excellent graphs in Jonathan Bober's answer.)

2) The author discusses the "eñe product" as a source of a mathematical explanation for his observation, and he refers to his own unpublished manuscripts in which he introduces this product. Are these manuscripts available? Does anyone have any reference which defines the eñe product?

Finally, any insights into Marco's results would be much appreciated.

The histograms (produced in Mathematica) are of the deltas of the first 10000 zeros of $\zeta(s)$ falling in $[100, 110]$ and $[190, 200]$, respectively. The purple bars show the locations of the zeros.

Answer by Gene S. Kopp for Asymptotics of the growth rate of a group

2012-05-24T00:46:25Z

There is never a (finite) generating set with that property.

Consider a generating set $S=\{x_1,\ldots,x_{\ell}\}$ of cardinality $\ell$. Let $B_k := B_k(S)$, $S_k := B_k \setminus B_{k-1}$, and $g := gr(S)$. Let $b_k := |B_k|$ and $s_k: = |S_k|$. Assume for simplicity that $L := \lim_{k \to \infty} \frac{b_k}{g^k}$ exists (although it shouldn't be difficult to get general liminf bounds). Also set $$ L' := \lim_{k \to \infty} \frac{s_k}{g^k} = \lim_{k \to \infty} \frac{b_k-b_{k-1}}{g^k} = \left(1-\frac{1}{g}\right)L. $$

For the spheres, there's a trivial inequality $s_{m+n} \leq s_m s_n$. (Any word of minimal length $m+n$ in the generators may be written at least one way as a product of two words of minimal length $m$ and $n$.) This is already enough to give $L' \geq 1$, and thus $$ L \geq \frac{1}{1-\frac{1}{g}} > 1. $$

This is unsatisfying and still leaves the possibility that $L'=1$. Thus, I eliminate that possibility as well, by improving the trivial bound $s_{2k} \leq s_k^2$ to $s_{2k} \leq \left(1-\frac{1}{2\ell}\right)s_k^2$. This improvement (unlike the trivial improvement above) does not hold for monoids, so the extra cancellation comes (unsurprisingly) from the existance of inverses.

Specifically, fix $k$, let $E_i$ be the set of all elements of $S_k$ which may be written as a word of length $k$ ending in $x_i$, and let $E_{\ell+i}$ be the set of all elements of $S_k$ which may be written as a word of length $k$ ending in $x_i^{-1}$. Set $$ F_i = E_i \setminus \bigcup_{j < i} E_j, $$ so the $F_i$ are disjoint. Let $F_i'$ be the image of $F_i$ under the inversion map, and let $n_i = |F_i|$. The product of an element of $F_i$ and an element of $F_i'$ may be written with $2k-2$ letters (because the $x_i$ and $x_i^{-1}$ cancel), so those $n_i^2$ products are not in $S_{2k}$. Thus, we have $$ s_{2k} \leq s_k^2 - \sum_{i=1}^{2\ell} n_i^2. $$ By the Hölder inequality, we have $$ s_k = \sum_{i=1}^{2\ell} n_i \leq \sqrt{\sum_{i=1}^{2\ell} 1^2} \sqrt{\sum_{i=1}^{2\ell} n_i^2} $$ $$ \frac{s_k^2}{2\ell} \leq \sum_{i=1}^{2\ell} n_i^2. $$ Combining the inequalities gives $$ s_{2k} \leq \left(1-\frac{1}{2\ell}\right)s_k^2. $$ Dividing by $g^{2k}$ and sending $k \to \infty$ gives $$ L' \geq \frac{1}{1-\frac{1}{2\ell}} > 1. $$ For balls, we obtain the bound $$ L \geq \frac{1}{\left(1-\frac{1}{g}\right)\left(1-\frac{1}{2\ell}\right)}. $$ This bound is optimal for free generating sets of free groups.

I'd be interested in seeing what Kate's limit says (or don't say) about the underlying group. Can the lower bound I just gave be achieved for non-free groups? Can the limit generally be made arbitrarily close to $1$ by increasing the number of generators appropriately (as Misha speculated in the comments)? I'm far from an expert in combinatorial/asymptotic group theory, so I don't have good intuition for what intrinsic information this value holds.

Answer by Gene S. Kopp for Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?

2012-04-23T20:35:53Z

Let $A_n = \{a : a \equiv 1 \mod 2^n \mbox{ and } 2^{2^{n-1}} \leq a < 2^{2^{n}} - 2^{2^{n-1}}\}$ , and let $\displaystyle A = \bigcup_{n=1}^\infty A_n$.

Then, $A(x) >> \frac{x}{\log x}$, the gap sizes are $<< \sqrt{x}$, and $A$ contains infinitely many non-multiples of $m$ for every $m>1$.

However, $2^{2^n}$ cannot be written as a sum of fewer than $n-\log_2 n$ elements of $A$. To prove this, suppose the contrary; say $2^{2^{n}} = a_1 + \cdots + a_k$ for $k < n-\log_2 n$, $a_1 \leq \cdots \leq a_k$, $a_i \in A$. We know that $a_k \in A_n$, because if not, then all the $a_i < 2^{2^{n-1}}$, so, summing, $2^{2^n} < k \cdot 2^{2^{n-1}}$, implying $2^{2^{n-1}} < n$, which is false for positive $n$. One applies a similar argument to each of the partial sums of the $a_i$, in turn from largest to smallest, to show that $\displaystyle a_j \in \bigcup_{i=n-k+j}^n A_i$. In particular, each $a_j \equiv 1 \mod 2^{n-k+1}$, so the sum $2^{2^n} \equiv k \mod 2^{n-k+1}$. Thus, $2^{n-k+1} \mid k$; in particular, $2^{n-k+1} \leq k$. Using the bound $k < n-\log_2 n$ on both sides, we may deduce $2n < n-\log_2 n$, a contradiction.

For a possible fix, I would assume that $A$ is well-distributed modulo $m$ (for every $m$) in an appropriate sense. (I'm being purposefully vague here, and you might need something rather strong, like an analogue of Bombieri-Vinogradov). Good luck!

Answer by Gene S. Kopp for Are all zeros of $\Gamma(s) \pm \Gamma(1-s)$ on a line with real part = $\frac12$ ?

2012-03-24T22:55:58Z

I would like to expand on Guild of Pepperers's answer by noting that the zeros are essentially uniformly spaced and may easily be approximated to a high degree of accuracy. Using Stirling approximation, I obtained the formula $$ \Gamma\left(\frac12+it\right) = \sqrt{\frac{2\pi}{1+e^{-2\pi|t|}}}\exp\left(-\frac\pi2|t|+i(t\log|t|-t+\varepsilon(t))\right), $$ valid for real $t$, where the error $\varepsilon(t)$ is an odd, bounded, real-valued function asymptotically equal to $\frac{1}{24t}$. (Indeed, $\varepsilon(t)$ has asymptotic and convergent expansions coming from the asymptotic and convergent versions of Stirling approximation, respectively.) We then have, for $s = \frac12+it$ on the critical line, $$ \Gamma(s)+\Gamma(1-s) = 2\sqrt{\frac{2\pi}{1+e^{-2\pi|t|}}}e^{-\frac\pi2|t|}\cos\left(t\log|t|-t+\varepsilon(t)\right), $$ $$ \Gamma(s)-\Gamma(1-s) = 2\sqrt{\frac{2\pi}{1+e^{-2\pi|t|}}}e^{-\frac\pi2|t|}\sin\left(t\log|t|-t+\varepsilon(t)\right). $$ One may show by means fair or foul that $t\log|t|-t+\varepsilon(t)$ is monotonically increasing for $|t|\geq1.05$, is bounded between $-0.96$ and $0.96$ for $|t|<1.05$, and is only zero when t = 0. Therefore, the zeros of $\Gamma(s)+\Gamma(1-s)$ on the critical line occur, with multiplicity one, very near those $t$ for which $t\log|t|-t$ is an odd integer multiple of $\frac{\pi}{2}$, and similarly for $\Gamma(s)-\Gamma(1-s)$ and the even integer multiples of $\frac{\pi}{2}$.

It's interesting that the number of zeros up to a given height $T$ is of the same order of magnitude, $T \log(T)$, as for the Riemann zeta function, but that these zeros have (essentially) uniform spacings rather than GUE spacings.

Perron-Frobenius "inverse eigenvalue problem"

2010-08-12T06:36:26Z

The Perron-Frobenius theorem says that the largest eigenvalue of a positive real matrix (all entries positive) is real. Moreover, that eigenvalue has a positive eigenvector, and it is the only eigenvalue having a positive eigenvector.

Now suppose we want to construct a positive rational matrix with a particular Perron-Frobenius eigenvalue. Specifically, consider a positive real algebraic number $\lambda$ which is greater in absolute value than all of its Galois conjugates. Does there exist a positive rational matrix $A$ with $\lambda$ as its Perron-Frobenius eigenvalue?

Answer by Gene S. Kopp for Showing e is transcendental using its continued fraction expansion

2010-09-25T19:02:42Z

To use the continued fraction for a number to prove it's transcendental, one usually shows that the rational approximations it affords are "too good" for an algebraic number. The traditional tool here is Liouville's theorem, but this has been improved to the more powerful Roth's theorem:

If $\alpha$ is algebraic, then for every $\varepsilon > 0$ there are only finitely many rational numbers $p/q$ satisfying $$ \left|\alpha - \frac{p}{q}\right| < \frac{1}{q^{2+\epsilon}}. $$

Unfortunately, $e$ also satisfies this. Indeed, rational approximations to $e$ are uncommonly bad. As Wadim mentions, there are only finitely many $p/q$ satisfying the following inequality. $$ \left|e - \frac{p}{q}\right| < \frac{\log \log q}{3 q^2 \log q}. $$

But Khinchin proved that, for almost all $\alpha$, $$ \left|\alpha - \frac{p}{q}\right| < \frac{1}{q} \phi(q) $$ has infinitely many solutions if and only if $\sum_q \phi(q)$ diverges.

Additionally, Khinchin showed that the geometric means of the entries of the continued fraction expansion of a real number almost always converge to a universal constant. The geometric means of the entries of the continued fraction expansion of $e$ diverge.

If either of Khinchin's conditions hold for nonquadratic algebraic numbers, the transcendentality of $e$ would follow, but a proof is probably out of reach.

Finally, the continued fraction expansion of $e$ provides an immediate proof of its irrationality, because rational numbers have finite continued fraction expansions. We also have that $e$ is not a quadratic irrational, because those have (eventually) periodic continued fraction expansions.

Answer by Gene S. Kopp for Examples of non-rigorous but efficient mathematical methods in physics

2010-12-10T08:11:05Z

The use of random matrix theory to model energy levels of heavy nuclei and other physical systems. See also the following historical piece and the pictures therein: There is striking statistical evidence that the eigenvalues of large random self-adjoint matrices, the energy levels of heavy nuclei, and the normalized zeros of $L$-functions (!) are all spaced about the same.

Is every compact topological ring a profinite ring?

2010-12-09T05:43:20Z

There are a lot of compact (Hausdorff) groups, whereas every compact field is finite. What about rings? Is there a classification theorem for compact rings? If you take a cofiltered limit of finite rings, you get a compact ring; for example, the $p$-adic integers $\mathbb{Z}_p$ are obtained as a limit of $$ \cdots \twoheadrightarrow \mathbb{Z}/p^{n+1}\mathbb{Z} \twoheadrightarrow \mathbb{Z}/p^n\mathbb{Z}\twoheadrightarrow \cdots \twoheadrightarrow \mathbb{Z}/p\mathbb{Z}\twoheadrightarrow 0. $$ Can every compact ring be obtained as a cofiltered limit of finite rings?

For a counterexample, a compact ring that is not totally disconnected would suffice. In the other direction, proving that such a ring has to be totally disconnected wouldn't suffice a priori: It would show the the additive group is profinite, but not that the ring is a cofiltered limit of rings.

Remark: By "compact," I consistently mean "compact Hausdorff."

Answer by Gene S. Kopp for A single paper everyone should read?

2010-11-17T08:42:58Z

Not technically a paper but a lecture (in pdf form) full of pretty pictures and cool ideas:

The Mysteries of Counting: Euler Characteristic versus Homotopy Cardinality by John Baez.

We all know what it means for a set to have 6 elements, but what sort of thing has -1 elements, or 5/2? Believe it or not, these questions have nice answers. The Euler characteristic of a space is a generalization of cardinality that admits negative integer values, while the homotopy cardinality is a generalization that admits positive real values. These concepts shed new light on basic mathematics. For example, the space of finite sets turns out to have homotopy cardinality e, and this explains the key properties of the exponential function. Euler characteristic and homotopy cardinality share many properties, but it's hard to tell if they are the same, because there are very few spaces for which both are well-defined. However, in many cases where one is well-defined, the other may be computed by dubious manipulations involving divergent series---and the two then agree! The challenge of unifying them remains open.

Answer by Gene S. Kopp for Sexy vacuity ....

2010-11-14T22:34:07Z

One is not a prime number, but zero is! It's different than the other prime numbers in $\mathbb{Z}$, though, because it has height zero rather than height one.

Zero is prime in any integral domain. Remember that the trivial ring is not an integral domain.

Answer by Gene S. Kopp for Sexy vacuity ....

2010-11-14T22:24:17Z

Zero is a limit ordinal, because it is the union of its elements.

Transfinite induction has two canonical statements. The "strong" statement, $$ (\forall \alpha,\beta)((\beta<\alpha) \wedge P(\beta) \rightarrow P(\alpha))\rightarrow (\forall \alpha)P(\alpha), $$ doesn't split anything into cases. The version used most frequently in proofs says that any property preserved under unions and successors holds for all ordinals. Zero should rarely be a special case.

Also, "limit ordinals" should totally be called "colimit ordinals". The term "limit ordinal" refers to limit points in the order topology, thus excluding zero, but this is silly.

Density of first-order definable sets in a directed union of finite groups

2010-10-27T23:10:17Z

This is a generalization of the following question by John Wiltshire-Gordon.

Consider an inductive family of finite groups: $$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \hookrightarrow \ldots $$

We may view each group as a subgroup of the next. Let $G$ be the directed union of the $G_i$: $$ G := \bigcup_{i=0}^\infty \ G_i $$

Now, $G$ is a countable group. Suppose we're asked a question like, "What proportion of the elements of $G$ are commutators?", or "What proportion of pairs $(g,h) \in G^2$ satisfy $g^2h^2=1$ but $g^2 \neq 1$?" We try to make sense of such questions in terms of density on $G^n$, which is not defined for all subsets. For $E \subseteq G^n$, let $$ d(E) := \lim_{i \to \infty} \frac{|E \cap G_i^n|}{|G_i^n|}, $$ if the limit exists.

My question is: If $E$ is a subset of $G^n$ that is first-order definable in the language of groups, does the density of $E$ necessarily exist? John's question covers the (still unresolved) special case of when $E$ is defined by an atomic formula.

A first-order definable subset $E \subseteq G^n$ is the set of $n$-tuples of group elements where a particular first-order formula in $n$ free variables is true. Such a formula is a finite string of symbols and may involve multiplication, inversion, the identity element, equality, logical connectives ($\wedge$, $\vee$, $\neg$, $\implies$), quatifiers ($\exists$ and $\forall$), and parentheses. For example, the following first-order formula defines the set of commutators $g \in G$:

$$ (\exists x)(\exists y)(g = xyx^{-1}y^{-1}). $$

On the other hand, if you try to define the commutator subgroup by such a formula, you run into trouble. You might want to say, "$g$ is a commutator or $g$ is a product of two commutators or $g$ is a product of three commutators or ...," but infinite disjunctions are not allowed.

Please note that the counterexample to a similar question in a comment by Vipul Naik here is not a counterexample to this question. In the inductive family $$ A_3 \hookrightarrow S_3 \hookrightarrow \ldots \hookrightarrow A_{2i-1} \hookrightarrow S_{2i-1} \hookrightarrow A_{2i+1} \hookrightarrow S_{2i+1} \hookrightarrow \ldots, $$ the groups alternate between having all the elements as commutators and half the elements as commutators. However, in the directed union, which is $A_\infty$, all the elements are commutators. The upshot is that quantifiers in a first-order formula may demand that you "look ahead" in your inductive family.

Answer by Gene S. Kopp for Efficiently getting bits of N! ?

2010-10-13T23:10:05Z

This isn't a complete answer, but I can do it polynomially in $\log N$ and $M$. In other words, the problem isn't hard if $M$ is small.

Stirling's formula approximating $N!$ gives the first few terms of a convergent series for $\log(N!)$. Using this series, we may approximate $\log(N!)$ to any fixed degree of accuracy in polynomial time (in $\log N$). Indeed, if you work it out, you'll see that you can approximate $\log(N!)$ within $2^{-M}$ in $O(M^2 \log N \log\log N)$ time. (Recall $\log N \log\log N$ is the cost of multiplication with a fast Fourier transform; if you multiplied naively, it would be $(\log N)^2$.) Approximating $\log(N!)$ within $2^{-M}$ is exactly what it takes to get the first $M$ digits.

Your question is actually equivalent to: Can you quickly pull out any digit of $N!$? There are only about $N \log N$ digits, so $M$ is bounded by a polynomial in $N$. By the above, we can get digits near the beginning. Digits near the end will also be easy: The problem then reduces to modular arithmetic and divisibility considerations. But I have no idea whether there's a fast way to pull out digits in the middle.

Answer by Gene S. Kopp for Interesting applications (in pure mathematics) of first-year calculus

2010-08-13T02:33:18Z

A cool example: The intermediate value theorem may be used to prove the following theorem about continued fractions:

Let $\alpha>1$, and suppose that $$ \left|\alpha-\frac{p}{q}\right|<\frac{1}{2q^2}. $$ Then, $\dfrac{p}{q}$ is one of the convergents (truncated continued fractions) of $\alpha$.

Comment by Gene S. Kopp

2013-04-10T23:27:51Z

Another interesting point about the Bump and Ginzburg paper is that it provides a combinatorial interpretation for the $a_g$ assuming the existence of an involution on $G$ with certain properties.

Comment by Gene S. Kopp

2013-04-10T23:24:51Z

Bump and Ginzburg remark on page 4 of their paper "Generalized Frobenius-Schur Numbers" that the Mathieu group $M_{11}$ provide another example where some of the $a_g$ are negative (and that the observation goes back to Solomon and Thompson). @David, your example is smaller (order 1920 versus 7920), so maybe it is not well-known.

Comment by Gene S. Kopp

2013-02-27T05:36:07Z

From a practical point of view, an easy way to check if you are right or wrong is to appeal to CM theory. In Mathematica, RootApproximant[KleinInvariantJ[Sqrt[-6]]] gives $1399+988\sqrt{2}$. The j-invariant generates the HCF, so Milne is right.

Comment by Gene S. Kopp

2012-07-16T23:47:54Z

Nice argument. Thanks for the answer!

Comment by Gene S. Kopp

2012-07-16T23:46:57Z

+1. Ah, of course. The product sigma-algebra contains only sets $\mathcal{S}$ of sets of real numbers in which membership $S \in \mathcal{S}$ is determined by membership $s \in S$ for countably many real numbers $s$. Thanks!

Comment by Gene S. Kopp

2012-05-25T00:07:19Z

@Allen & Dan: My analysis professor saying, "turn your head 90 degrees" was quite helpful the first time I learned Lebesgue integration. In retrospect, I usually choose to think of the two the theories as "approximation by step functions" and "approximation by simple functions," so both are adding up rows.

Comment by Gene S. Kopp

2012-05-24T23:57:05Z

@Harry: I used to think more or less the same thing, but while teaching calculus I found that: (1) Many students had the false belief that the Riemann integral was defined as an anti-derivative. (2) Many students seemed genuinely interested in understanding the geometry of Riemann integration even though they hadn't been interested in other non-computational topics. Even for mathematicians, the geometric intuition of integration as signed area is more important/fundamental than any of its many definitions. Thus, conveying that intuition should be the first goal of teaching integration.

Comment by Gene S. Kopp

2011-12-23T20:50:37Z

@JSE: I would be very interested to see if Marco's observation has a function field analogue.

Comment by Gene S. Kopp

2011-12-23T20:48:14Z

@JSE: I don't think this should be thought of as a fact about the distribution of γ1−γ2−γ3. Marco observes that the deltas of zeros of Dirichlet L-functions repel the zeros of ζ(s)...NOT their own zeros! So, for this phenomenon to be visible on the random matrix side would mean that the eigenvalues of a random Hermitian operator will predict the locations of zeta zeros. I doubt that; instead, Marco's observation deals with the finer properties of $L$-function zeros that are not shared with random matrices.

Comment by Gene S. Kopp

2011-12-09T04:43:15Z

@Harry: Thanks, I fixed it.

Comment by Gene S. Kopp

2011-04-29T07:51:07Z

József Pelikán told me that every finite poset can be realized as the spectrum of a ring (although I don't have a reference). A crucial point is that you can obtain closed and open subspaces by ring quotients and localizations, respectively. So the real challenge is building a ring with a big, complicated spectrum with the posets you want as subspaces. I enjoyed constructing examples by hand for some small posets; it's a nice exercise.

Comment by Gene S. Kopp

2011-01-24T06:17:25Z

Denis, I think you mean "e.g., the direct sum of all finite groups," not the direct product. The direct product of all finite groups is a profinite group, is not torsion, and satisfies both (1) and (2).

Comment by Gene S. Kopp

2010-12-09T10:27:04Z

Yes, this appears to be the argument in Stroppel's book as well (see comments). Thanks for the reference!

Comment by Gene S. Kopp

2010-12-09T09:55:40Z

Gjergji: Thanks for the reference!

Comment by Gene S. Kopp

2010-12-03T11:15:09Z

True :) I just think things should have names and definitions that reflect the way they're most often used.