# P3750: Minimum telephone-gossip time on the five by five torus

- ID: `P3750`
- Reference: `torus-five-gossip-rounds`
- Page: https://theoremdb.org/statements/P3750
- 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/torus-five-gossip-rounds?representation=markdown
- Record maturity: Reviewed problem

## The problem

Each vertex of \(C_5\square C_5\) initially knows a unique rumor. In one synchronous round, the edges of any matching may be used for calls, and callers exchange everything they know. Determine the minimum number of rounds until every vertex knows all 25 rumors.

### Remarks

- **Remark.** A vertex participates in at most one call per round.
- **Remark.** Knowledge is copied rather than moved, and a call exchanges the complete knowledge sets present at the start of that round.
- **Remark.** The schedule is fixed in advance; no failures or choices occur during execution.

### What counts as a solution

- Give a schedule of T matchings and a temporal-cut, information-flow, or exhaustive-search certificate proving T-1 rounds impossible.

## Status

**Resolution status:** Open.
**Lean verification:** Not Lean-verified.

A Lean formalization is attached. Signed verification is pending.

## Research packet

### Background and intake notes

A four-round all-gossip schedule on one five-cycle can be run on all rows in parallel and then on all columns.

- Propagate 25-bit knowledge masks through a candidate sequence of matchings to verify an upper certificate.
- The information-doubling lower bound gives five rounds, but graph locality and matching congestion should strengthen it.
- Schedules equivalent under torus automorphisms and time reversal can be merged in a breadth-first search.

- Recorded example: On C5, the four matchings {(0,1)}, {(1,2),(3,4)}, {(0,1),(2,3)}, {(1,2),(4,0)} spread all five rumors.

### Computational notes

- Bitmask replay verified the displayed C5 schedule. Applying it simultaneously to the five rows, followed by its transpose on the five columns, gives an eight-round torus schedule. Since one vertex can know at most 2^t rumors after t rounds, at least five rounds are necessary.

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `torus-five-gossip-rounds`, 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.