Ups and downs of first order sentences on random graphs

Shelah and Spencer [1] proved that the zero-one law holds for the first ord er sentences on random graphs G(n,n(-alpha)) whenever cu is a fixed positiv e irrational. This raises the question what zero-one valued functions on th e positive irrationals arise as the limit probability of a, first order sen tence on these graphs. Here we prove two necessary conditions on these func tions, a number-theoretic and a complexity condition. We hope to prove in a , subsequent paper that these conditions together with two simpler and prev iously proved conditions are also sufficient and thus they constitute a cha racterization.