For all positive integers n and k, if M is an n-dependent structure, R(y_1,…,y_m) is a relation definable in M, and f_i:X_i^r_i→ M are arbitrary functions with r_i≤ k for 1≤ i≤ m, then the composed relation S(barx_1,…,barx_m) defined by S(barx_1,…,barx_m)mathrelLongleftrightarrowR bigl(f_1(barx_1),…,f_m(barx_m)bigr) is kn-dependent.

Composition conjecture for n-dependence

For all positive integers $n$ and $k$ , if $M$ is an $n$ -dependent structure, $R(y_1,\ldots,y_m)$ is a relation definable in $M$ , and $f_i:X_i^{r_i}\to M$ are arbitrary functions with $r_i\leq k$ for $1\leq i\leq m$ , then the composed relation $S(\bar{x}_1,\ldots,\bar{x}_m)$ defined by $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 $kn$ -dependent.

References

Primary source

arXiv

Additional references

The Composition Lemma for n-dependence — arXiv

classification-theory model-theory

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

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 $n$ -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=2$ .
A later preprint states a general composition lemma for arbitrary finite arity $k$ , presenting it as Theorem $3.24$ .

September 1, 2026 claimed confirmation

On September 1, 2026, the preprint The Composition Lemma for $n$ -dependence claimed to confirm the Chernikov–Hempel conjecture and to show that the factor $kn$ 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 $kn$ is claimed sharp in general, but both claims remain unverified.

Sources

No solutions have been posted yet.