You are currently browsing the category archive for the ‘guest blog’ category.

[This guest post is authored by Ingrid Daubechies, who is the current president of the International Mathematical Union, and (as she describes below) is heavily involved in planning for a next-generation digital mathematical library that can go beyond the current network of preprint servers (such as the arXiv), journal web pages, article databases (such as MathSciNet), individual author web pages, and general web search engines to create a more integrated and useful mathematical resource. I have lightly edited the post for this blog, mostly by adding additional hyperlinks. - T.]

This guest blog entry concerns the many roles a World Digital Mathematical Library (WDML) could play for the mathematical community worldwide. We seek input to help sketch how a WDML could be so much more than just a huge collection of digitally available mathematical documents. If this is of interest to you, please read on!

The “we” seeking input are the Committee on Electronic Information and Communication (CEIC) of the International Mathematical Union (IMU), and a special committee of the US National Research Council (NRC), charged by the Sloan Foundation to look into this matter. In the US, mathematicians may know the Sloan Foundation best for the prestigious early-career fellowships it awards annually, but the foundation plays a prominent role in other disciplines as well. For instance, the Sloan Digital Sky Survey (SDSS) has had a profound impact on astronomy, serving researchers in many more ways than even its ambitious original setup foresaw. The report being commissioned by the Sloan Foundation from the NRC study group could possibly be the basis for an equally ambitious program funded by the Sloan Foundation for a WDML with the potential to change the practice of mathematical research as profoundly as the SDSS did in astronomy. But to get there, we must formulate a vision that, like the original SDSS proposal, imagines at least some of those impacts. The members of the NRC committee are extremely knowledgeable, and have been picked judiciously so as to span collectively a wide range of expertise and connections. As president of the IMU, I was asked to co-chair this committee, together with Clifford Lynch, of the Coalition for Networked InformationPeter Olver, chair of the IMU’s CEIC, is also a member of the committee. But each of us is at least a quarter century older than the originators of MathOverflow or the ArXiv when they started. We need you, internet-savvy, imaginative, social-networking, young mathematicians to help us formulate the vision that may inspire the creation of a truly revolutionary WDML!

Some history first.  Several years ago, an international initiative was started to create a World Digital Mathematical Library. The website for this library, hosted by the IMU, is now mostly a “ghost” website — nothing has been posted there for the last seven years. [It does provide useful links, however, to many sites that continue to be updated, such as the European Mathematical Information Service, which in turn links to many interesting journals, books and other websites featuring electronically available mathematical publications. So it is still worth exploring ...] Many of the efforts towards building (parts of) the WDML as originally envisaged have had to grapple with business interests, copyright agreements, search obstructions, metadata secrecy, … and many an enterprising, idealistic effort has been slowly ground down by this. We are still dealing with these frustrations — as witnessed by, e.g., the CostofKnowledge initiative. They are real, important issues, and will need to be addressed.

[This article was guest authored by Frank Morgan, the vice president of the American Mathematical Society.]
The American Mathematical Society (AMS) has launched a new blog

[This post is authored by Timothy Chow.]

I recently had a frustrating experience with a certain out-of-print mathematics text that I was interested in.  A couple of used copies were listed at over \$150 a pop on Bookfinder.com, but that was more than I was willing to pay.  I wrote to the American Mathematical Society asking if they were interested in bringing the book back into print.  To their credit, they took my request seriously, and solicited the opinions of some other mathematicians.

Unfortunately, these referees all said that the field in question was not active, and in any case there was a more recent text that was a better reference.  So the AMS rejected my proposal.  I have to say that I was surprised, because the referees did not back up their opinions with any facts, and I knew that in addition to the high price that the book commanded on the used-book market, there was some circumstantial evidence that it was in demand.  A MathSciNet search confirmed my belief that, contrary to what the referees had said, the field was most definitely active.  Plus, another text on the same subject that Dover had recently brought back into print had a fine Amazon sales rank (much higher than that of the recent text cited by the referees).

A colleague then suggested that maybe I should instead contact the author directly, asking him to regain the copyright from the publisher.  The author could then make the book available on his website or pursue print-on-demand options, if conventional publishers were not interested. I tried this, but was again surprised to discover that the author thought it was not worth the trouble to get the copyright back, let alone to make the text available.  Again the argument was that, allegedly, nobody was interested in the book.

In both cases I was frustrated because I did not know how to find other people who were interested in the same book, to prove to the AMS or the author that there were in fact many of us who wanted to see the book back in print.

Now for the good news.  After hearing my story, Klaus Schmid promptly set up a prototype website at

Anyone can go to this site and suggest a book, or vote for books that others have suggested.  This is precisely the kind of information that I believe would have greatly helped me argue my case.  Of course, the site works only if people know about it, so if you like the idea, please spread the word to your friends and colleagues.

It might be that a better long-term solution than Schmid’s site is to convince a bookselling website to tally votes of this sort, because such a site will catch users “red-handed” searching for an out-of-print book.  I have tried to contact some sites with this suggestion; so far, Booksprice.com and Fetchbook.info have said that they like the idea and may eventually implement it.  In the meantime, hopefully Schmid’s site will  become a useful tool in its own right.

Let me conclude with a question.  What else can we be doing to increase the availability of out-of-print books, especially those that are still copyrighted?  Several people have told me that the solution is for authors to regain the copyrights to their out-of-print books and make their books available themselves, but authors are often too busy (if they are not deceased!).  What can we do to help in such situations?

[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. - T.]

The entropy-influence conjecture seeks to relate two somewhat different measures as to how a boolean function has concentrated Fourier coefficients, namely the total influence and the entropy.

We begin by defining the total influence. Let $\{-1,+1\}^n$ be the discrete cube, i.e. the set of $\pm 1$ vectors $(x_1,\ldots,x_n)$ of length n. A boolean function is any function $f: \{-1,+1\}^n \to \{-1,+1\}$ from the discrete cube to {-1,+1}. One can think of such functions as “voting methods”, which take the preferences of n voters (+1 for yes, -1 for no) as input and return a yes/no verdict as output. For instance, if n is odd, the “majority vote” function $\hbox{sgn}(x_1+\ldots+x_n)$ returns +1 if there are more +1 variables than -1, or -1 otherwise, whereas if $1 \leq k \leq n$, the “$k^{th}$ dictator” function returns the value $x_k$ of the $k^{th}$ variable.

We give the cube $\{-1,+1\}^n$ the uniform probability measure $\mu$ (thus we assume that the n voters vote randomly and independently). Given any boolean function f and any variable $1 \leq k \leq n$, define the influence $I_k(f)$ of the $k^{th}$ variable to be the quantity

$I_k(f) := \mu \{ x \in \{-1,+1\}^n: f(\sigma_k(x)) \neq f(x) \}$

where $\sigma_k(x)$ is the element of the cube formed by flipping the sign of the $k^{th}$ variable. Informally, $I_k(f)$ measures the probability that the $k^{th}$ voter could actually determine the outcome of an election; it is sometimes referred to as the Banzhaf power index. The total influence I(f) of f (also known as the average sensitivity and the edge-boundary density) is then defined as

$I(f) := \sum_{k=1}^n I_k(f).$

Thus for instance a dictator function has total influence 1, whereas majority vote has total influence comparable to $\sqrt{n}$. The influence can range between 0 (for constant functions +1, -1) and n (for the parity function $x_1 \ldots x_k$ or its negation). If f has mean zero (i.e. it is equal to +1 half of the time), then the edge-isoperimetric inequality asserts that $I(f) \geq 1$ (with equality if and only if there is a dictatorship), whilst the Kahn-Kalai-Linial (KKL) theorem asserts that $I_k(f) \gg \frac{\log n}{n}$ for some k. There is a result of Friedgut that if $I(f)$ is bounded by A (say) and $\varepsilon > 0$, then f is within a distance $\varepsilon$ (in $L^1$ norm) of another boolean function g which only depends on $O_{A,\varepsilon}(1)$ of the variables (such functions are known as juntas).

[This post is authored by Alexandre Borovik. An extended version of this post, with further links and background information, can be found on Alexandre's blog.]

I had never in my life seen an arrested blackboard encircled by a police tape, still with some group theory problems on it.

But this had actually happened when the Turkish authorities closed
down the Mathematical Summer School
run by Ali Nesin for Turkish undergraduate students; Ali Nesin may face prosecution for an Orwellian offence of “education without permission“. Please sign the online petition in his support.
Read the rest of this entry »

[This post is authored by Emmanuel Kowalski.]

This post may be seen as complementary to the post “The parity problem in sieve theory“. In addition to a survey of another important sieve technique, it might be interesting as a discussion of some of the foundational issues which were discussed in the comments to that post.

Many readers will certainly have heard already of one form or another of the “large sieve inequality”. The name itself is misleading however, and what is meant by this may be something having very little, if anything, to do with sieves. What I will discuss are genuine sieve situations.

The framework I will describe is explained in the preprint arXiv:math.NT/0610021, and in a forthcoming Cambridge Tract. I started looking at this first to have a common setting for the usual large sieve and a “sieve for Frobenius” I had devised earlier to study some arithmetic properties of families of zeta functions over finite fields. Another version of such a sieve was described by Zywina (“The large sieve and Galois representations”, preprint), and his approach was quite helpful in suggesting more general settings than I had considered at first. The latest generalizations more or less took life naturally when looking at new applications, such as discrete groups.

Unfortunately (maybe), there will be quite a bit of notation involved; hopefully, the illustrations related to the classical case of sieving integers to obtain the primes (or other subsets of integers with special multiplicative features) will clarify the general case, and the “new” examples will motivate readers to find yet more interesting applications of sieves.

[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. - T.]

This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points. More precisely, we fix a dimension d and make the following definition (introduced by Haussler and Welzl):

• Definition: Let $X \subset {\Bbb R}^d$ be a finite set of points, and let $0 < \epsilon < 1$. We say that a finite set $Y \subset {\Bbb R}^d$ is a weak $\epsilon$-net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that $|B \cap X| > \epsilon |X|$, then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong $\epsilon$-net for X with respect to convex bodies.)

For example, in one dimension, if $X = \{1,\ldots,N\}$, and $Y = \{ \epsilon N, 2 \epsilon N, \ldots, k \epsilon N \}$ where k is the integer part of $1/\epsilon$, then Y is a weak $\epsilon$-net for X with respect to convex bodies. Thus we see that even when the original set X is very large, one can create a $\epsilon$-net of size as small as $O(1/\epsilon)$. Strong $\epsilon$-nets are of importance in computational learning theory, and are fairly well understood via Vapnik-Chervonenkis (or VC) theory; however, the theory of weak $\epsilon$-nets is still not completely satisfactory.

One can ask what happens in higher dimensions, for instance when X is a discrete cube $X = \{1,\ldots,N\}^d$. It is not too hard to cook up $\epsilon$-nets of size $O_d(1/\epsilon^d)$ (by using tools such as Minkowski’s theorem), but in fact one can create $\epsilon$-nets of size as small as $O( \frac{1}{\epsilon} \log \frac{1}{\epsilon} )$ simply by taking a random subset of X of this cardinality and observing that “up to errors of $\epsilon$“, the total number of essentially different ways a convex body can meet X grows at most polynomially in $1/\epsilon$. (This is a very typical application of the probabilistic method.) On the other hand, since X can contain roughly $1/\epsilon$ disjoint convex bodies, each of which contains at least $\epsilon$ of the points in X, we see that no $\epsilon$-net can have size much smaller than $1/\epsilon$.

Now consider the situation in which X is now an arbitrary finite set, rather than a discrete cube. More precisely, let $f(\epsilon,d)$ be the least number such that every finite set X possesses at least one weak $\epsilon$-net for X with respect to convex bodies of cardinality at most $f(\epsilon,d)$. (One can also replace the finite set X with an arbitrary probability measure; the two formulations are equivalent.) Informally, f is the least number of “guards” one needs to place to prevent a convex body from covering more than $\epsilon$ of any given territory.

• Problem 1: For fixed d, what is the correct rate of growth of f as $\epsilon \to 0$?

[This post is authored by Ben Green, who has kindly "guest blogged" this week's "open problem of the week". - T.]

In an earlier blog post Terry discussed Freiman’s theorem. The name of Freiman is attached to a growing body of theorems which take some rather “combinatorial” hypothesis, such that the sumset |A+A| of some set A is small, and deduce from it rather “algebraic” information (such that A is contained in a subspace or a grid).

The easiest place to talk about Freiman’s theorem is in the finite field model ${\Bbb F}_2^n$ (see my survey article on this subject for a full discussion). Here it was shown by Ruzsa that if |A+A| is at most $K |A|$ then A is contained in a subspace of size no more than about $2^{K^4}|A|$. The exponent has been improved a few times since Ruzsa’s paper, the best result currently in print being due to Sanders, who obtains an upper bound of $2^{K^{3/2}\log K}|A|$. Terry and I are in the process of writing a paper which obtains $2^{2K + o(K)}|A|$, which is best possible in view of the example $A := \{e_1,...,e_m\}$ where $m := 2K + O(1)$; this set has doubling roughly K but is not contained in a subspace of dimension smaller than 2K.

This result has an air of finality (except for the true nature of the o(K) term, which represents an interesting open problem). This is something of an illusion, however. Even using this theorem, one loses an exponential every time one tries to transition between “combinatorial” structure and “algebraic” structure and back again. Indeed if one knows that A is contained in a subspace of size $2^{2K}|A|$ then the strongest assertion one can make about the doubling of A is that it is at most $2^{2K}$.

The Polynomial Freiman-Ruzsa conjecture (PFR), in ${\Bbb F}_2^n$, hypothesises a more precise structure theorem for sets with small doubling. Using this
conjecture, one may flit back and forth between combinatorial and algebraic structure with only polynomial losses. Ruzsa attributes the conjecture to
Marton: it states that if A has doubling at most K then A is contained in the union of $K^{O(1)}$ translates of some subspace H of size at most |A|.