Relation Algebra and Sumset Problems in Abelian Groups

Abstract: An abstract relation algebra (RA) is called representable if it embeds in a collection of binary relations closed under union, complementation, composition, conversion, and identity. The question of representability is undecidable for finite RAs. It is therefore of interest to impose various restrictions on the RAs or on the representations themselves in order to narrow the search space.

For example, one might consider only so-called "cyclic" representations, which affords a log-quadratic improvement in search time. If we further assume that the automorphism group of the algebra A with c "colors" (symmetric diversity atoms) contains a cycle of length c, and consider only those cyclic representations that arise via a finite field method (due to Comer), we actually get decidability: we can check for Comer representations of A in O(c^8 / log c) time.

If an RA A has no 3-cycles ("rainbow triangles"), then representability of A is decidable without restriction on the "type" of representation, a result due to Maddux.

A "Goldilocks" happy medium might be found by restricting attention to representations over abelian groups more generally. In this context, problems can be stated in terms of sumset conditions for partitions of the group. For example,

For which finite abelian G does there exist a partition G = {0} u A u B such that

• A = -A
• B = -B
• A + A = G
• A + B = G \ {0}
• B + B = {0} u A ?

This formulation has two real advantages: first, the problem is understandable to any mathematician; second, we can bring in results from the additive number theory literature.

Notice that the set B above is a sum-free set. Constructing sum-free sets with other desired properties is difficult in general. We will discuss this in the context of a problem I've been working on for almost 20 years.

discrete mathematicscombinatoricslogic

Audience: researchers in the topic

---

Online logic seminar

Series comments: Description: Seminar on all areas of logic

---