Random finite functions -- standard and nonstandard

A. Woods (logic seminar)

Abstract:

Suppose F is a collection of specially labelled trees (i.e. a forest). Suppose that each type of branch appears 0 modulo q times. Does q divide |F| ? This, of course, depends on the underlying labelling set and the specific rules of how the trees are labelled. I consider labellings which are determined by two numbers p and n. A naive conjecture states that for each (q,p,n) there are only such forests (excluding trivial counter examples) when q divides |F|. It turn out that there exists 'exceptional' forests which violate this naive conjecture. There exists forinstance (q=3, p=9 and n=30) a forests which contains 16821302548060 trees (\neq 0 modulo 3) and where each branch appears 0 modulo 3 times. I conjecture that whenever certain strongly symmetrical equations have a solution thay actually have a symmetrical solution. This conjecture allows a complete classification of all exceptional forests. The conjecture have close links to algebra (representation theory), mathematical logic (bounded arithmetic) and complexity theory (length of propositional proofs). I present some conjectures which despite many efforts remains unsolved.