On the volumes and affine types of trades

Abstract

A $[t]$-trade is a pair $T=(T_{+},T_{-})$ of disjoint collections of subsets (blocks) of a $v$-set $V$ such that for every $0\le i\le t$, any $i$-subset of $V$ is included in the same number of blocks of $T_{+}$ and of $T_{-}$. It follows that $|T_{+}|=|T_{-}|$ and this common value is called the volume of $T$. If we restrict all the blocks to have the same size, we obtain the classical $t$-trades as a special case of $[t]$-trades. It is known that the minimum volume of a nonempty $[t]$-trade is $2^t$. Simple $[t]$-trades (i.e., those with no repeated blocks) correspond to a Boolean function of degree at most $v-t-1$. From the characterization of Kasami--Tokura of such functions with small number of ones, it is known that any simple $[t]$-trade of volume at most $2\cdot 2^t$ belongs to one of two affine types, called Type\,(A) and Type\,(B) where Type\,(A) $[t]$-trades are known to exist. By considering the affine rank, we prove that $[t]$-trades of Type\,(B) do not exist. Further, we derive the spectrum of volumes of simple trades up to $2.5\cdot 2^t$, extending the known result for volumes less than $2\cdot 2^t$. We also give a characterization of "small" $[t]$-trades for $t=1,2$. Finally, an algorithm to produce $[t]$-trades for specified $t$, $v$ is given. The result of the implementation of the algorithm for $t\le 4$, $v\le 7$ is reported.

30 pages, final version, to appear in Electron. J. Combin