# P3720: Minimum XOR circuit for an eight-tap cyclic transform

- ID: `P3720`
- Reference: `circulant-sixteen-xor-circuit`
- Page: https://theoremdb.org/statements/P3720
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: f295905458d7a3b058de2e38a46a52071c41c31e
- Current Markdown: https://api.theoremdb.org/v1/statements/circulant-sixteen-xor-circuit?representation=markdown
- Record maturity: Reviewed problem

## The problem

Over \(\mathbb F_2\), map sixteen input bits to \(y_i=x_i+x_{i+1}+x_{i+3}+x_{i+4}+x_{i+7}+x_{i+8}+x_{i+10}+x_{i+11}\), with indices modulo 16. Determine the minimum number of fanout-free-cost, two-input XOR gates in a straight-line circuit computing all sixteen outputs.

### Remarks

- **Remark.** Inputs and wire fanout have zero cost; every gate outputs the XOR of two earlier wires and costs one.
- **Remark.** Outputs may name input wires or gate outputs at no extra cost.
- **Remark.** The objective is unrestricted linear straight-line complexity, so gates need not respect cyclic symmetry.

### What counts as a solution

- Give a straight-line program using g XOR gates and a complete SAT, meet-in-the-middle, or linear-circuit lower certificate excluding g-1 gates.

## Status

**Resolution status:** Open.

No proof or formalization has been recorded.

## Research packet

### Background and intake notes

The direct independent computation costs 112 gates, leaving ample room for shared intermediates and a crisp exact endpoint.

- The cyclic factorization supplies a symmetric 48-gate circuit, while an optimum may deliberately break symmetry to share other partial sums.
- Cancellation means set-union reasoning is unsound for lower bounds; every wire is a vector in a sixteen-dimensional binary space.
- A SAT certificate should state wire ordering, allowed reuse, and whether duplicate gate values are forbidden by normalization.

- Recorded example: Compute \(u_i=x_i+x_{i+1}\), then \(v_i=u_i+u_{i+3}\), then \(y_i=v_i+v_{i+7}\), with all indices modulo 16.

### Computational notes

- The three cyclic layers in the displayed construction use 16 gates each, for an upper bound of 48. Symbolic expansion of every output produced exactly the eight requested taps, with no duplicate term. Independent output-by-output XOR trees would use 16 times 7, or 112, gates.

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `circulant-sixteen-xor-circuit`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.