Equivalence of FO- and FOM-transductions

Let

scr C$ and

scr D$ be infinite classes of finite graphs. An FO-transduction interprets graphs using first-order formulas, while an FOM-transduction allows first-order formulas with modular counting. The FO–FOM transduction conjecture.

$$\mathscr D \text{ is an FOM-transduction of } \mathscr C \quad\Longleftrightarrow\quad \mathscr D \text{ is an FO-transduction of } \mathscr C.$$

The conjecture asks whether modular counting increases the power of first-order transductions on infinite classes of finite graphs. The paper presents this as an unresolved question arising from the fact that it is not clear whether FOM-transductions are more powerful than FO-transductions in general.