On circular external difference families

Circular external difference families (CEDFs) are a recently-introduced variation of external difference families (EDFs) with applications to non-malleable threshold schemes: a $(v,m,\\ell,1)$-CEDF is an $m$-sequence $(A_0, \\ldots, A_{m-1})$ of $\\ell$-subsets of an additive group $G$ of order $v$ such that $G\\setminus\\{0\\}$ equals the multiset of all differences $a-a'$, with $(a,a')\\in A_{i+1}\\times A_{i}$ for some $i \\in \\mathbb{Z}_m$. When $G$ is the cyclic group, we speak of a cyclic CEDF. The existence of cyclic $(v,m,\\ell,1)$-CEDFs is well understood when $m$ is even, while nonexistence is known when both $m$ and $\\ell$ are odd. However, the case where $m$ is odd and $\\ell$ is even has only been resolved in a few special cases. In this paper, we address this gap by constructing cyclic $(v,m,\\ell,1)$-CEDFs for any odd $m>1$ when $\\ell=2$, and for any even $\\ell \\ge 2$ when $m=3$. Notably, the latter result relies on the existence of a suitable tiling of the multiplicative semigroup of $\\mathbb{Z}_v\\setminus\\{0\\}$. Moreover, noting that every $(v,3,\\ell,1)$-CEDF produces a $(v,3,\\ell,2)$-EDF, we completely solve the existence problem for $(3\\ell^2+1,3,\\ell,2)$-EDFs over an abelian group. Our approach is based on representing the blocks as arithmetic progressions and analyzing their step patterns. We present two different ways to construct cyclic $(v,m,2,1)$-CEDFs for every odd $m>1$; their step patterns show that the resulting CEDFs are inequivalent. Many additional inequivalent CEDFs are obtained by translating suitable subsets within the CEDF.