User mike - MathOverflow

Cliques, Paley graphs and quadratic residues

2010-12-07T22:15:18Z

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.

If p=1 mod 4 is a prime, we can define the Paley graph, call it $P(p)$, of order p as follows. This graph has vertex set {0, 1, 2, ...., p-1} with two vertices i and j joined by an edge if and only if i - j is a quadratic residue modulo p. If p=1 mod 4 then -1 is a quadratic residue modulo p so this is a bona fide undirected graph. Say $c(p)$ is the clique number, or size of the largest complete subgraph of $P(p)$.

We can ignore graphs, etc. and just phrase it in terms of finding a maximum set, A, of quadratic residues modulo p (p still is 1 modulo 4) such that the difference of any two distinct elements of A is still a quadratic residue.

I'll make several comments here at this point:

There are the "standard bounds" which are of the form $c(p) > (1/2-o(1)) lg(p)$ and

$c(p) < sqrt(p)$ where $lg(p)$ is the base 2 logarithm.
One or both of these bounds have been rediscovered every 5-10 years or so, going all the way back to Erdos and Newman(?) back in the 1950's. Sometime soon, I'll collect a comprehensive list and make it available online. :::::grin:::::: Another interesting observation is that both bounds can be proved either using combinatorial tools (Ramsey's theorem, Lovasz's theta function, SDP and vertex transitive graphs, etc.) OR using number theoretic tools (Gaussian sums, Weil's theorem, etc.)
We can look at generalizations involving quadratic nonresidues, nonprime finite fields/rings, etc. which I won't get into, though I can at least refer to Ernie Croot's problem list in arithmetic combinatorics and work of Gasarch and Ruzsa. I'm not interested ( in this post at least:::grin::::) in this.

Finally my question: Has anyone been able to materially improve either of these bounds?

What I do know about related work is:

Maistrelli and Penman give a discussion of these bounds along with some computational work, in Discrete Mathematics in 2006.
Fan Chung, Friedlander, Iwaniec and others have studied related problems in character sums and applications in combinatorics but haven't seemed to show (yet?) any improvement in the bounds for $c(p)$. Or, have I missed something obvious here?
Andrew Thomason, Chung-Graham-Wilson, etc. have related work on "pseudo-random graphs" which I will assume is known, or at least accessible to all the readers here. Thomason, in one article, makes some interesting assertions which are plausible but which I need to check.
There's the work of a number of people from Alon to Wigderson, exploring related questions and their applications to problems in theoretical computer science.
Finally, we have estimates for $n(p)$, the least quadratic nonresidue modulo p, following Chowla, Salie, Graham-Ringrose and others. The connection with $c(p)$ is obvious.

What else, of a substantial nature, is there?

I think, in particular, that using work of Granville and Soundarajan, the 1/2 in the first bound can be improved and using a combination of number theoretic methods (Burgess, etc.) and combinatorial methods (Ruzsa, Chang, Green, etc.) the second (square root) bound can be improved. I'm going to stop here and not go into any more specifics, either attempts, propositions, conjectures or computational evidence.

Exotic spheres and stable homotopy in all large dimensions?

2009-11-07T05:59:36Z

Given that the kervaire invariant one problem has been solved in (almost) all dimensions....my question is whether there exists an exotic sphere in all sufficently lagre dimensions? Given the Kervaire-Milnor theory this "quasireduces" to determining whether coker J has nontrivial stable homotopy in all large dimensions. Has anyone looked at this? I've glanced at the work of Ravenel, etc. which doesn't seem to be sufficent.

Small maximal sets with no 3-AP?

2011-11-04T21:03:49Z

Everyone knows about the problem of finding the largest set in 1,2,...,N which contains no arithmetic progression of length 3.....what happens if we look at the set which is the smallest maximal subset of 1,...,N which contains no 3-AP?

Obviously we have a square root lower bound using a greedy argument and a simple upper bound, with exponent log(2)/log(3), by looking at integers with no 2 in their base 3 representation. Is anything better known, in either direction? I know about the original work of Stanley and Odlyzko.......

Answer by Mike for Exotic spheres and stable homotopy in all large dimensions?

2009-11-07T07:54:55Z

Yes. For some progressions mod 4 this follows easily.

A more general question I could ask is for any fixed prime p and any large n there is a nontrivial p-element in the stable homotopy group of dimension n and/or the group of exotic spheres of dimension n?

I could say more here about Kervaire, Milnor, Bernoulli and others but I'll desist(for now:::grin:::).

Answer by Mike for Can one make Erdős's Ramsey lower bound explicit?

2009-11-07T07:43:42Z

A question I have here is what do you mean by "explicit"?

Personally, I like the definition that a construction is explicit if it can be constructed in polynomial time (due to Alon? Wigderson??). Given that we are talking about exponentials in n here, this gets (slightly) complicated, but we'll say the controlling parameter here is N=2^n, the rough order of the number of vertices in a possible Ramsey graph.

One conjecture I have is that the set of Paley graphs on p vertices, where p ranges over all primes 1(mod 4) between 2^(n/2) and 2^(n-1) gives a lower bound on R(n). This is NOT an explicit set, by my definition above. ::::grin:::::

If memory serves me, I think the best result known for your original question is in a paper of Noga Alon from a few yrs back. You may want to check his web page as well as Gasartch's survey page mentioned before.

Answer by Mike for How can you tell if a space is homotopy equivalent to a manifold?

2009-11-07T07:08:09Z

I'm relying on memory here. A good example, which is discussed in Madsen and Milgram's book on surgery and classifying spaces for topological, PL and smooth manifolds is the set of 1-connected Poincare duality spaces of dimension 5 with 4-skeleton h. e. to the 4-skeleton of (S^2) x (S^3), which is (S^2) v (S^3).

::::: sorry, M. O. won't let me use image tags :( ::::::::

a, (S^2) x (S^3), which is obviously a manifold

b. a manifold homeomorphic to SU(3)/SO(3) (though this fact isn't mentioned in Madsen & Milgram).

c. a Poincare duality space whose Spivak fibration cannot be reduced to a smooth vector bundle. This is proved using secondary cohomology operations based on Steenrod squares. This was first proven by Gitler and Spivak(?).

Comment by Mike

2011-11-06T16:25:25Z

Kevin, here's a link to the work that Odlyzko and Stanley did on greedy sequences: dtc.umn.edu/~odlyzko/unpublished Also, Odlyzko has some comments here on later work. There is also a couple of articles in Discrete Mathematics, one by Erods and coauthors, which are relevant. I've been thinking about this topic on and off over the past few days and may write up what little I have.

Comment by Mike

2011-11-04T20:29:34Z

Ben, thanks. I'll email him about this later, after I think about it for a little while.

Comment by Mike

2011-11-04T20:28:18Z

Yes, you're right Seva. My apologies. :) I'll have to write you later, re: followup/questions to 1 or 2 of your papers. Thanks.

Comment by Mike

2011-03-21T00:10:47Z

Yes, here it is: people.math.gatech.edu/~ecroot/E2S-01-11.pdf especially Sect. 2.8.

Comment by Mike

2010-12-08T02:27:23Z

They are examples of 1-connected Poincare duality spaces of dimension 5. If you ignore cohomology operations they look homologically like a manifold. The space in c is a Poincare duality space which cannot be homotopy equivalent to a manifold, I believe. This is due to the "higher" homotopy structure which is implicit in (non)vanishing Steenrod operations. Sean, I'll try to find you a more explicit reference for this. For now, I would say, look at the first 2-4 chapters of the PUP book of Brumfiel-Madsen-Milgram.

Comment by Mike

2009-11-09T07:08:23Z

Gil, thanks for your comment. I like the log space condition on 'explicit constructions' as stronger(?) than P time.