Let p be a fixed prime number and N be a large integer. The "Inverse Conjecture for the Gowers Norm" states that if the "d-th Gowers norm" of a function f:FNp to Fp is non-negligible, that is larger than a constant independent of N, then f has a non-trivial correlation with a degree d-1 polynomial. The conjecture is known to hold for d=2,3 and for any prime p. In this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. Essentially the same result, with different bounds for correlation, was independently obtained by Green and Tao. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime p, for d = p2.

A set S in the vector space F/sub p//sup n/ is "good" if it satisfies any of the following (almost) equivalent conditions: (1) S are the rows of a generating matrix for a linear distance code, (2) all (nontrivial) Fourier coefficients of S are bounded away from 1, and (3) the Cayley graph on F/sub p//sup n/ with generators S is a good expander A good set S must have at least cn vectors (with c > 1). We study conditions under which S is the orbit of only a constant number of vectors, under the action of a finite group G on the n coordinates. Such succinctly described sets yield very symmetric codes, and can "amplify" small constant-degree Cayley expanders to exponentially larger ones. For the regular action (the coordinates are named by the elements of the group G), we develop representative theoretic conditions on the group G which guarantee the existence (in fact, abundance) of such few expanding orbits. The condition is a (nearly tight) upper bound on the distribution of dimensions of the irreducible representations of G, and is the main technical contribution of this paper We further show a class of groups for which this condition is implied by the expansion properties of the group G itself! By combining these, we can iterate the amplification process above, and give (near-constant degree) Cayley expanders which are built from Abelian components. For other natural actions, such as of the affine group on a finite field, we give the first explicit construction of such few expanding orbits.

(MATH) A set S in the vector space FFpn is "good" if it satisfies the following (almost) equivalent conditions:

A shared directional multichannel (SDM) consists of a set of inputs and a set of outputs to which transmitters and receivers respectively, are connected. A signal placed at any given input reaches a subset of the outputs, and a channel is specified by the sets of outputs that are reachable from each input. A message is received successfully at an output of the channel if and only if it is addressed to the receiver connected to that output and no other signals reach that output at the same time. Constructive lower bounds as well as some upper bounds on the uniform-traffic capacity of SDM-based single-hop interconnections between a set of multitransmitter source stations and a set of multireceiver destination stations are derived. A bidirectional interconnection among a set of stations can be obtained by representing each station as one source station and one destination station. It is shown that with randomized transmissions, SDMs that can be described as a collection of buses can perform as well as any other channels. With deterministic scheduling, however, the use of certain non-bus-oriented SDMs yields a much higher interconnection capacity.>