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$?