co.combinatorics - Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

This is a good question which is the subject of intensive research in mathematics and theoretical computer science. The blog (which is the serialization of a book in progress) "Analysis of Boolean Functions" by Ryan O'Donnell is a good source, and so is the Book: Lectures on noise sensitivity and percolation by Garban and Steif.

Here is some information

1) Of course, the Fourier coefficients of real functions over the discrete cube can be arbitrary. The question is therefore what restrictions apply for Boolean functions.

Boolean functions are characterized by $f^2(x)=1$ and since product translates to convolution for the Fourier transform, being Boolean is characterized by a property of the Fourier transform convolved with itself. However, this characterization by itself is not very useful.

Parseval formula asserts that for Boolean functions the sum of square of the Fourier
coefficients is 1. It also give the following formula for the variance of $f$,
$$operatorname{var}(f) = sum { hat f^2(S): S ne emptyset } $$

2) An important tool which gives much information is Bonami (or Bonami–Gross–Beckner) inequality. It asserts that for every function $f$, $$|T_epsilon (f) |_2 le |f| _{1+epsilon^2}.$$
This implies that if $f$ has values $0$, $1$, and $-1$ and the the support of $f$ has measure $t$ then most of the Fourier spectrum of $f$ is for $S$ with $|A|> log n/10$ (say).

3) A similar reasoning gives the so called KKL's theorem. It asserts that for a Boolean function $f$ there is an index $k$ so that $$sum { hat f^2(S): S subset [n], i in S } ge operatorname{var}(f) log n/n.$$

4) A theorem of Friedgut asserts that for a Boolean function $f$ if $sum hat f^2(S) |S|$ is bounded above by a constant $c$ then $f$ is "$epsilon$-close" to a "Junta. " A Junta is a Boolean function depending on a bounded number $C$ of variables. ($C$ is a function of $c$ and $epsilon$.)

5) A theorem by Green and Sanders from the paper Boolean functions with small spectral norm, asserts that a Boolean function all whose Fourier coefficients are bounded by $M$ is a linear combination of bounded number $(le 2^{2^{O(M^4)}}$) of characteristic functions of subspaces.

6) A result by Talagrand asserts that for a Boolean functions $f_n$ if $sum_i^nhat f_n^2({i})$ is o(1) then so is $sum_i^nhat f_n^2({i})$. An extension of this result to higher levels was given by Benjamini, Kalai and Schramm, and a sharp quantitative version by Keller and Kindler.

7) A theorem of Bourgain asserts that for a Boolean function if the decay of the Fourier coefficients squared is larger than quadratic in $|S|$, then again $f$ is approximately a Junta.

8) There is a conjecture called the Entropy influence conjecture that asserts that $sum hat f^2 (S)|S|$ is bounded from below by an absolute constant times $sum hat f^2(S) log (hat f^2(S))$.

cv.complex variables - Infinite-dimensional complex polynomial or rational Lie algebras and their pseudogroups

In studying the transformation groups generated by holomorphic vector fields V(z) d/dz on ℂ, I've noticed the (surely well-known) fact that the complex quadratic vector fields:

            {(a z² + b z + c) d/dz  |  (a,b,c) ∊ ℂ³}

form precisely the Lie algebra whose nonzero elements generate the linear fractional transformations, i.e., PSL(2,ℂ).

• Is there some underlying reason for this? (Beyond direct calculation, which provides an easy proof.)

Other than the further Lie algebras {0}, {a d/dz}, and {(a z + b) d/dz} over ℂ of trivial, constant, and linear (affine) vector fields, there seem to be no other polynomial finite-dimensional Lie algebras of vector fields on ℂ.

• Is there some easy-to-explain reason for this?

The next "simplest" such polynomial Lie algebras of vector fields on C seem to be those defined by all polynomial and all rational functions:

(*)        V_P := {P(z) d/dz  |  P(z) ∊ C[z]}   and   V_R := {R(z) d/dz  |  R(z) ∊ C(z)}.

• Contrariwise, do there exist finite-dimensional Lie algebras of vector fields on ℂ defined by rational functions -- other than the polynomial ones mentioned above?




• In case V_P and/or V_R generate well-studied (infinite-dimensional) Lie "groups" of transformations from open sets of ℂ into open sets, then what are these groups? Properly, these are pseudogroups, but perhaps they behave like Lie groups.

[Note: It's not hard to compute formulas for such transformations -- the flows -- directly from an expression for the vector field in terms of its zeroes (and poles, if any).]

• In any case, are there standard names for the Lie algebras V_P and V_R ?




• References to the above matters would also be appreciated.

Two questions on isomorphic elliptic curves

Question 1: Putting both curves in say, Legendre Normal Form (or else appealing the lefschetz principle) shows that if the two curves are isomorphic over $mathbf{C}$ then they are isomorphic over $overline{mathbf{Q}}$. Now we could say that for instance $E_2$ is an element of $H^1(G_{overline{Q}}, Isom(E_1))$ where we let $Isom(E_1)$ be the group of isomorphisms of $E_1$ as a curve over $mathbf{Q}$ (as in Silverman, to distinguish from $Aut(E_1)$, the automorphisms of $E_1$ as an Elliptic Curve over $mathbf{Q}$, that is, automorphisms fixing the identity point). However, $E_2$ is also a principle homogeneous space for a unique curve over $mathbf{Q}$ with a rational point, which of course has to be $E_2$, so the cocycle $E_2$ represents could be taken to have values in $Aut(E_1)$. Now $Aut(E_1)$ is well known to be of order 6,4 or 2 depending on whether the $j$-invariant of $E_1$ is 0, 1728 or anything else, respectively. Moreover the order of the cocycle representing $E_2$ (which we now see must divide 2, 4 or 6) must be the order of the minimal field extension $K$ over which $E_1$ is isomorphic to $E_2$. So $K$ must be degree 2,3,4 or 6 unless I've made an error somewhere.

Question 2: If you restrict your focus to just elliptic curves, yes your idea is right. If it's a quadratic extension, you have exactly 1 non-isomorphic companion. If you have a higher degree number field, you have nothing but composites of the quadratic case unless your elliptic curve has j invariant 0 or 1728.

Notice I am very explicitly using your choice of the word elliptic curve for both of these answers.

When is an algebra of commuting matrices (contained in one) generated by a single matrix?

Thanks for the answers. Just to wrap up a bit, here are a few examples.

1) Sometimes an ACM (algebra of commuting matrices) is sure to be generated by one of its members

2) Other times it has dimension too large to possibly be (embedded in) an ACM with a single generator.

3) An ACM might be generated by 2 matrices, not generated by any of its members, but embed in a larger ACM which does have a single generator.

4) An ACM might be generated by 2 matrices, not generated by any of its members, but not embed in a larger ACM which does have a single generator (even in the 3x3 case).

1) If the matrices are all normal then they can be simultaneously diagonalized. This reduces the problem to an algebra of diagonal matrices, which is easy to understand. Such an algebra is actually generated by one of its members.

2) The 5 dimensional algebra ${cal{A}}_5$ mentioned by Mariano (4x4 matrices with 2x2 blocks $left(begin{smallmatrix}0&A\0&0end{smallmatrix}right)$ has dimension too large to be generated by a single matrix. Furthermore, each member M generates only the 2 dimensional algebra of matrices $jI+kM$ so no subalgebra of dimension 3 or 4 has a single generator.

3) Consider the subalgebra ${cal{A}}_3$ of ${cal{A}}_5$ generated by $left(begin{smallmatrix}0&A\0&0end{smallmatrix}right)$ and $left(begin{smallmatrix}0&B\0&0end{smallmatrix}right)$ with A and B 2x2 invertible matrices (neither a scalar multiple of the other). As mentioned, we can't embed ${cal{A}}_3$ in a singly generated 4 dimensional subalgebra of ${cal{A}}_5$
However it also embeds in other 4 dimensional algebras.

For example a 4x4 matrix $left(begin{smallmatrix}BA^{-1}&C\0&A^{-1} Bend{smallmatrix}right)$ will generate an ACM which commutes with everything in ${cal{A}}_3$. I guess in this case it would automatically contain ${cal{A}}_3$. I certainly verified that randomly filling in the C does this in several cases. In many cases I tested one can get away with one or both of A and B having rank 1... but not always. The two 4x4 matrices made from matrices with $A=left(begin{smallmatrix}1&0\0&0end{smallmatrix}right)$ and $B=left(begin{smallmatrix}0&1\0&0end{smallmatrix}right)$ give an example of that. One can shrink this to 3x3 (in the case that the underlying ring is $mathbb{Z}_2$ as noted by Martin and missed by me), so I will:

4) The two $3 times 3$ matrices $left(begin{smallmatrix}0&1&0\0&0&0\0&0&0end{smallmatrix}right)$ and $left(begin{smallmatrix}0&0&1\0&0&0\0&0&0end{smallmatrix}right)$ generate an algebra A with eight members $left(begin{smallmatrix}a&b&c\0&a&0\0&0&aend{smallmatrix}right)$.
A is maximal but not generated by any of its members as each member generates a 2 dimensional (or smaller) subalgebra.

lie algebras - Is this an identity in Lie bialgebras?

Perhaps this will be a trivial question. For this post, everything is over your favorite field of characteristic $0$.

Definitions and notation

Recall that a Lie algebra is a vector space $mathfrak g$ along with a map $beta: mathfrak g^{wedge 2} to mathfrak g$ satisfying the Jacobi identity. One way to write the Jacobi identity is as follows: extend $beta$ to $mathfrak g^{otimes 2} to mathfrak g$ via the usual projection $mathfrak g^{otimes 2} to mathfrak g^{wedge 2}$, consider the map $beta circ (1 otimes beta): mathfrak g^{otimes 3} to mathfrak g$; then the restriction of this map to $mathfrak g^{wedge 3} subseteq mathfrak g^{otimes 3}$ vanishes. (Because $beta$ vanishes on the symmetric product $mathfrak g^{vee 2}$, the Jacobi identity is equivalent to $beta circ (1 otimes beta)$ vanishing on $mathfrak g^{vee 3}$.)

A Lie coalgebra is a vector space $mathfrak g$ with a map $delta: mathfrak g to mathfrak g^{wedge 2}$, satisfying the coJacobi identity, which asserts that the map $(delta otimes 1) circ delta: mathfrak g to mathfrak g^{wedge 3}$ vanishes. A vector space $mathfrak g$ that is both a Lie algebra (under $beta$) and a Lie coalgebra (under $delta$), is a Lie bialgebra if $beta$ and $delta$ satisfy an additional relationship. Namely, let $sigma: mathfrak g^{otimes 2} to mathfrak g^{otimes 2}$ be the usual "flip" map; then the bialgebra identity is that $delta circ beta$ and $(1 otimes beta)circ (delta otimes 1) + (beta otimes 1) circ (1 otimes delta) + (beta otimes 1) circ (1otimes sigma) circ (delta otimes 1) + (1 otimes beta) circ (sigma otimes 1) circ (1 otimes delta)$ are equal as maps $mathfrak g^{otimes 2} to mathfrak g^{otimes 2}$.

My question

In a calculation I'm doing, I'm led to consider the map $mathfrak g^{otimes 2} to mathfrak g^{vee 3}$ given by $(1 otimes beta otimes 1) circ (delta otimes delta)$. (I mean, $(1 otimes beta otimes 1) circ (delta otimes delta)$ lands in $mathfrak g^{otimes 3}$, but I want the composition with the natural projection $mathfrak g^{otimes 3} to mathfrak g^{vee 3}$.) In particular, for the calculation to come out right, I'd like for this map to vanish. Does it?

discrete geometry - Is there a dense subset of the real plane with all pairwise distances rational?

Let me answer Question 2.

Strong version: no. Consider $[0,1]$ with distance $d(x,y)=|x-y|^{1/3}$. There is no even a triple of points with rational distances - otherwise there would be a nonzero rational solution of $x^3+y^3=z^3$.

Weak version: yes. Let $(X,d)$ be the space in question. Construct sets $S_1subset S_2subsetdots$ such that each $S_k$ is a maximal $(2^{-k})$-separated net in $X$. Let $S$ be the union of these nets; then $S$ is countable and dense in $X$.

Now construct the following metric graph on $S$. For every $k$, connect every pair of points $x,yin S_k$ by an edge whose length is $(1-10^{-k})d(x,y)$ rounded down to a multiple of $10^{-2k}$. The new distance $d'$ on $S$ is the induced length distance in this graph. It is easy to see that the edges outside $S_k$ do not affect the distances in $S_k$, hence all these distances are rational (multiples of $10^{-2k}$). The new metric $d'$ on $S$ satisfies $frac12dle d'le d$, hence the completion of $(S,d')$ is the same set $X$ with an equivalent metric.

UPDATE.
Here is a more detailed description without the term "metric graph".

For each $k$, define a function $f_k:mathbb R_+tomathbb R_+$ by
$$
f_k(t) = 10^{-2k}leftlfloor 10^{2k}(1-10^{-k})t rightrfloor .
$$
The actual form of $f_k$ does not matter, we only need the following properties:

• $f_k$ takes only rational values with bounded denominators (by $10^{-k}$).




• Let $a_k$ and $b_k$ denote the infimum and the supremum of $f_k(t)/t$ over the set ${tge 2^{-k}}$. Then $frac12le a_kle b_kle a_{k+1}le 1$ for all $k$. (Indeed, we have $1-2cdot10^kle a_kle b_kle 1-10^k$.)

For every $x,yin S_k$, define $ell(x,y)=f_k(d(x,y))$ where $k=k(x,y)$ is the minimum number such that $x,yin S_k$. Note that
$$
a_k d(x,y) le ell(x,y) le b_k d(x,y)
$$
for all such pairs $x,y$, since $S_k$ is a $(2^{-k})$-separated set. For a finite sequence $x_0,x_1,dots,x_nin S$ define
$$
ell(x_0,x_1,dots,x_n) = sum_{i=1}^n ell(x_{i-1},x_i) .
$$
I will refer to this expression as the $ell$-length of the sequence $x_0,dots,x_n$. Define
$$
d'(x,y) = inf{ ell(x_0,x_1,dots,x_n) }
$$
where the infimum is taken over all finite sequences $x_0,x_1,dots,x_n$ in $S$ such that $x_0=x$ and $x_n=y$. Clearly $d'$ is a metric and $frac12dle d'le d$. It remains to show that $d'$ takes only rational values.

Lemma: If $x,yin S_k$, then $d'(x,y)$ equals the infimum of $ell$-lengths of sequences contained in $S_k$.

Proof: Consider any sequence $x_0,dots,x_n$ in $S$ such that $x_0=x$ and $y_0=y$. Remove all points that do not belong to $S_k$ from this sequence. I claim that the $ell$-length became shorter. Indeed, it suffices to prove that
$$
ell(x_r,x_s) le ell(x_r,x_{r+1},dots,x_{s-1},x_s)
$$
if $x_r$ and $x_s$ are in $S_k$ and the intermediate points are not. By the second property of the functions $f_k$, the left-hand side is bounded above by $b_k d(x_r,x_s)$ and every term $ell(x_i,x_{i+1})$ in the right-hand side is bounded below by $b_k d(x_i,x_{i+1})$. So it suffices to prove that
$$
b_k d(x_r,x_s) le b_ksum_{i=r}^{s-1} d(x_i,x_{i+1}),
$$
and this is a triangle inequality multiplied by $b_k$. Q.E.D.

All $ell$-lengths of sequences in $S_k$ are multiples of some fixed rational number (namely $10^{-2k}$). Hence $d'(x,y)$ is a multiple of the same number if $x,yin S_k$. Thus all values of $d'$ are rational.

What are natural questions to ask about an operad?

Hi Connie. Let me use your question as an excuse for an extended answer.
A pair of brief papers "Definitions: operads, algebras and modules" and
"Operads, algebras and modules", which are available at
http://www.math.uchicago.edu/~may/PAPERS/mayi.pdf
and http://www.math.uchicago.edu/~may/PAPERS/handout.pdf (# 84,85 on my website)
give several variants and reformulations of the original definition together with
some history of antecedents, a variety of algebraic and topological examples,
and the crucial relationship with monads that led me to coin the word "operad".
There is also a discussion of the relationship to homological algebra, showing
how the homological theory simplifies if you work over a field of characteristic
zero and, in contrast, how operads encode homology operations (Steenrod operations
and Dyer-Lashof operation) if you work over a field of finite characteristic. Notes
for a talk, http://www.math.uchicago.edu/~may/TALKS/SwitzerlandTalk.pdf, expand on
the last point.

The distinction of characteristic illustrates a general point. Operads are defined
in any symmetric monoidal category, and the right questions to ask depend in large
part on what category you are working in. It may make no sense at all to ask
algebraic questions of a topological operad or topological questions of an algebraic
operad. There is also a distinction to be made about questions to ask about operads
and questions to ask about their algebras. Incidentally, groups are by design not
examples of algebras over an operad: to define inverses, you need diagonals, and
operads are not intended, or rather intended not, to incorporate such structure.
The questions to ask also depend on what role your observation plays. Operads
allow a taxonomy of certain types of algebraic structures, so the question may just
be "what kind of structure am I looking at".

But you might also want to ask whether the algebras you are looking at give simpler
"approximations'' of more complicated or less accessible structures that occur "in
nature". For example, spaces $Omega^nSigma^n X$ occur in nature, but they can
very usefully be approximated by the monads $C_nX$ associated to appropriate operads.

You might also want to ask if operads can be used to define rigorously new structures
that you want to study. A very recent example arose in work of Bertrand Guillou and myself
in equivariant infinite loop space theory: there is an intuition of what a genuine
strict symmetric monoidal $G$-category should be, one that gives rise to a genuine
$G$-spectrum; the best definition we know is that such a category is an algebra
over a particular operad in $Cat$ (see http://front.math.ucdavis.edu/1207.3459).
Quite a few recent variants of the definition of an operad arose analogously.

In algebra, very simple operads prescribe very natural and previously unstudied
kinds of algebras. Loday and some of his students (I'm blanking on names) gave a number of examples.

While one can ask questions about the homotopy theory of operads in general,
using model category theory, that is perhaps my least favorite question to
ask: it rarely cuts to the heart of the applications, excepting those in higher
category theory, or so it seems to me. Model categories of algebras
over particular operas do play a major role in many applications, albeit
sometimes only implicitly.

I'll stop here, since I could go on forever.

One comment. While the Martin-Shnider-Stasheff book is a useful compendium, its treatments
of different topics are not all at the same level, and you might well prefer less
comprehensive treatments that better address your directions of interest. And people
should be warned that the definition of an operad in that book is actually incorrect: it omits a
crucial equivariance property that is of real importance in applications. For example, it plays a
key role in the proof of the Adem relations for the Steenrod and Dyer-Lashof operations.
Benoit Fresse's book "Modules over operads and functors" gives a quite different take
on operads, with a focus on modules over algebras over operads.