A circulant coin weighing problem

Question

We are given $n$ coins, some of which are "real" and weigh $1$ and some of which are "fake" and weigh $0$. We have one "spring scale" which can weigh any subset of the coins. A classic question asks what the minimum number of weighings is that will separate the real coins from the fake ones. This question is essentially identical to Number of vectors so that no two subset sums are equal and the optimal number of weighings is known to be asymptotic to

$$\frac{2n}{\log_2{n}}.$$

The linked question contains a reference to Bshouty where further details and an interesting historical account can be found. The original paper of Erdős and R\'enyi discussing this coin weighing problem is also available.

For a fixed $n$, a (non-adaptive) solution to this coin weighing problem can be written as a $(0,1)$-matrix, with each column corresponding to a coin and each row corresponding to a single weighing. The number of rows is then the number of weighings. In order for such a matrix to solve the problem, it must not contain any non-zero $n$-dimensional $(-1,0,1)$-vector in its kernel. Clearly, the identity matrix, for example, always satisfies this property and is a trivial solution for any $n$.

In my setting, I would like to solve the same coin weighing problem but I need any solution matrix to be (partial) ciculant. For example, consider $n=4$ and the following partial ciculant solution.

\begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1 \end{pmatrix}

This tells us that it is possible to solve the problem with $3$ weighings when $n=4$ and in fact this is optimal.

For this new circulant variant of the coin weighing problem I don't know anything except for particular small values of $n$ where I have manually computed the answer. However, these results are not particularly revealing except to tell us that the optimal number of weighings is not identical to the general case. For example, the problem can be solved in $7$ weighings for $12$ coins in the general case but you need $8$ weighings for the circulant case.

We know of course that an asymptotic lower bound is still $2n/\log_2{n}$. But an upper bound seems much less clear. As a first question:

Is the optimal number of weighings sublinear in $n$?

If this is true, then it would very interesting to know if the asymptotics differ from the general case.

Is the optimal number of weighings still $O(n/\log_2{n})$?

This question is related to the second part of Two conjectures about zero inner products and dissociated sets and can be seen as a variant of Conjecture 2.

---

A helpful answer was given with respect to a sparse version of this problem. However, I am really interested in the general non-sparse version where a solution matrix is guaranteed always to be able to separate the real and the fake coins.

---

Added 25 June 2015

Before addressing the questions above, is it possible to answer the following potentially easier question?

Does there exist a number of coins $n$ such that the optimal number of weighings is less than $n/2$?

Answer 1

Here's a rather indirect suggestion, using ideas from compressed sensing. Let $\Phi$ be your weighing matrix. Denote by $v$ your vector of coin weights and by $u$ the all ones vector. Observe that $\Phi(u-v) = \Phi u - \Phi v$. I'll assume in the remainder of this answer that either $v$ or $u-v$ is sparse (e.g. that either the number of the real coins or the number of the fake coins is less than $n^{1-\epsilon}$ for some positive $\epsilon$).

Compressed sensing (in a broad sense) was invented to efficiently recover sparse signals. Typical results in this area say that if a vector $x$ has length $N$ and $k$ non-zero entries, and if $\Phi$ is constructed appropriately, then $O(k \log N)$ measurements suffice to recovery $x$. The construction here very often involves taking the matrix entries independently from a probability distribution.

Now, you want to use a sub-matrix of a binary circulant matrix. Results of Rauhut-Romberg-Tropp ("Restricted Isometries for Partial Random Circulant Matrices") deal with circulant matrices. Calderbank and others have considered compressed sensing with binary matrices. To my knowledge no-one has tried to combine both properties. But my guess would be that some sort of similar recovery result would hold asymptotically for a random sub-matrix of a random circulant binary matrix. My guess would be that you'd get Big-O of the vector sparsity times some power of $\log N$. If I wanted to run simulations, I'd probably start with rows from the core of a Paley Hadamard matrix.

If you really care about the case that the numbers of real and fake coins are roughly equal, I'd suggest having a look at the literature on weighing matrices. There has been some study of circulant weighing matrices, though the literature has focussed on square matrices for the most part. See e.g. de Launey and Flannery's "Algebraic Design Theory" and the references therein. Best of luck!