← All problems

Composition conjecture for n-dependence

For all positive integers nn and kk, if MM is an nn-dependent structure, R(y1,…,ym)R(y_1,\ldots,y_m) is a relation definable in MM, and fi:Xiri→Mf_i:X_i^{r_i}\to M are arbitrary functions with ri≤kr_i\leq k for 1≤i≤m1\leq i\leq m, then the composed relation S(xˉ1,…,xˉm)S(\bar{x}_1,\ldots,\bar{x}_m) defined by S(xˉ1,…,xˉm)⟺R(f1(xˉ1),…,fm(xˉm))S(\bar{x}_1,\ldots,\bar{x}_m)\mathrel{\Longleftrightarrow}R\bigl(f_1(\bar{x}_1),\ldots,f_m(\bar{x}_m)\bigr) is knkn-dependent.

References

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to settle the conjecture and show its numerical bound is sometimes best possible.

The conjecture of Chernikov and Hempel concerns preservation of nn-dependence under composition with functions of bounded arity. The available sources do not give the conjecture’s original date.

Known results

  • Earlier work proves the binary composition case, with arity k=2k=2.
  • A later preprint states a general composition lemma for arbitrary finite arity kk, presenting it as Theorem 3.243.24.

September 1, 2026 claimed confirmation

On September 1, 2026, the preprint The Composition Lemma for nn-dependence claimed to confirm the Chernikov–Hempel conjecture and to show that the factor knkn cannot generally be improved. This is an unrefereed claim; the retrieved sources contain no independent verification or analysis of the sharpness assertion.

Current status (as of September 2026): The conjecture is claimed proved, and the factor knkn is claimed sharp in general, but both claims remain unverified.

Sources

Solutions 0

No solutions have been posted yet.