Phasor pleroma

The Pleroma: one exact hologram, many views

A fixed-size array of exact integers that stores a multiset of items, and answers counts by key, by flag word, by Hamming distance and by time from slices of that one array.

  • Experimental API

What it is

The Pleroma is a fixed-size array of exact integers (finite-field arithmetic) that stores a multiset of items. Each item is a key, optionally with flag bits, an ordering and a timestamp. One array answers many queries: counts by key, by flag word, by Hamming distance, and joint flag-and-time counts. Key queries refuse past capacity. The others never return a wrong count within the field's range.

The store holds a harmonic transform on the product of these groups: the key cycle, the flag cube, the symmetric group and the time cycle. A hologram is the transform itself, and each component of the transform is called a harmonic. The store keeps only the harmonics its views need, and each view reads its own slice of the array and nothing else.

The three faces

A Pleroma view is one of three faces of the same array.

Syzygy (the key cycle)
Key-addressed lookup: counts per key, and whole items (key, flags, arrangement and time together) with signed counts. It refuses past KeyCapacity distinct keys, returning false rather than a wrong answer.
Monad (the order face, S_k, 2 to 5)
Counts per arrangement of up to 5 things, even minus odd, and superposed readings of arrangement queries. Exact while counts stay within the field's range.
Ouroboros (the flag cube, up to 16 bits)
Counts per flag word, items within Hamming distance r of a query, the nearest words, and joint counts over flags and time. Exact while counts stay within the field's range.

The operation grid

The Pleroma implements a grid of operations on one exact hologram: 25 cells, 8 rungs by 3 faces, plus a lid and the relation and charge lattices. Each rung is a family of operations, one per face. Every cell is a public member of Pleroma with property tests against brute-force or naive implementations, and every whole-store operation applies to all items in one pass.

The pyramid on the Phasor page draws the same grid in three dimensions, with each cell's API and evidence.

Each rung is a family of operations, one per face
RungSyzygyMonadOuroboros
1. Pair (Logic)
Signed insertion, deletion, and bit toggle. Two copies cancel.
Signed insertion and deletionBinary choiceFlag toggle via XOR
2. Identity (Sets)
Lookup, one-hot categories, exact flag words at any load.
Key on the cycleOne-hot categoryBinary codes and Hamming retrieval
3. Relation (Algebra)
Bind: keys add, flags XOR, arrangements compose. All pairs in one pass.
Multiset composition via bindingArrangement compositionParity: odd-occurrence XOR
4. Function (Transforms)
Store as lookup table. Shifts as harmonics. Time-valued maps with opt-in TimeSpectrum.
Table and Fourier shiftOne-to-one map and balance checkBoolean function and Walsh spectrum
5. Symmetry (Automorphisms)
ScaleKeys (permute or gather). Conjugate arrangements. Frobenius x^2 on GF(2).
Key permutation and gatherConjugation of arrangementsGF(2) Frobenius: bit squaring
6. Composition (Products, Codes)
CRT pairing of key cycles. Linear bit maps. Hamming syndromes.
Chinese remainder theorem pairingIndependence testHamming syndromes
7. Turning (Dynamics)
Tick (exact rotation). Diffuse (Markov mixing). LFSR (shift registers).
Spiral on the time circleDiffusion: Markov mixingShift-register cycles (Galois LFSR)
8. Circulation (Topology)
Holonomy (winding). Current (Kolmogorov). Frustration (parity).
Winding number around a loopSteady-state current directionFrustration: loop parity

Superposition: one store, many items

One Pleroma holds many items at once. Every whole-store operation then applies to all of them in a single pass, and the cost of that pass does not depend on the number of items stored. Mixing different harmonic permutations (key scaling, bit maps and conjugation, rung 5) costs one pass per term.

The example holds three items with key capacity 4, then applies one kernel of 1x identity plus 2x (flip flag bit 0, age 1 tick). Press Replay to watch the pass move through the store, or switch between the counts before and after.

One pass, every item

Counts per flag word, counts per tick and the flags by time cells, before and after the pass. Every number is read from the real store.

Counts after the passCount per flag word: 000 is 6, 001 is 3, 010 is 2, 011 is 4, 100 is 1, 101 is 2, 110 is 0, 111 is 0. Count per time tick: 0 is 3, 1 is 6, 2 is 2, 3 is 4, 4 is 1, 5 is 2, 6 is 0. Count per flag word000600130102011410011012110111 Count per time tick0316223441526

Three items

Key 10, flags 001, time 0, count 31x to key 10, flags 001, time 0, count 32x to key 10, flags 000, time 1, count 6
Key 20, flags 010, time 2, count 21x to key 20, flags 010, time 2, count 22x to key 20, flags 011, time 3, count 4
Key 30, flags 100, time 4, count 11x to key 30, flags 100, time 4, count 12x to key 30, flags 101, time 5, count 2

kernel = 1x identity + 2x (flip flag bit 0, age 1 tick)

Counts before and after the pass
Count per flag word
Flag wordBeforeAfter
00006
00133
01022
01104
10011
10102
11000
11100
Count per time tick
TickBeforeAfter
033
106
222
304
411
502
600
Flags by time joint cells that are not zero after the pass
CellBeforeAfter
flags 000, tick 106
flags 001, tick 033
flags 010, tick 222
flags 011, tick 304
flags 100, tick 411
flags 101, tick 502
Generated by running the published EvaluatedApplications.Phasor package (release 2.17.0). Every number is the package's own output.

The kernel applies exactly the store you would get by moving every item by every element and adding the copies. The measured cost of the pass is on the evidence page, beside the cost of doing it item by item.

The code behind the example
using Phasor;

var store = new Pleroma(new HologramShape
{
    KeyCapacity = 4,
    FlagBits = 3,
    TimePeriod = 7,
    JointFaces = HologramFaces.Flags | HologramFaces.Time,
});
store.Add(new HologramItem(Key: 10, Flags: 0b001, Time: 0), 3);
store.Add(new HologramItem(Key: 20, Flags: 0b010, Time: 2), 2);
store.Add(new HologramItem(Key: 30, Flags: 0b100, Time: 4), 1);
Console.WriteLine("before flags " + string.Join(" ", store.Flags()));
Console.WriteLine("before times " + string.Join(" ", store.Times()));

// One kernel: 1x identity plus 2x (flip flag bit 0 and age one tick), applied to every item in one pass.
var kernel = new PleromaKernel(store.Shape);
kernel.Add(weight: 1L);
kernel.Add(flagMask: 0b001, timeShift: 1, weight: 2L);
store.Apply(kernel);

Console.WriteLine("after flags  " + string.Join(" ", store.Flags()));
Console.WriteLine("after times  " + string.Join(" ", store.Times()));
Output
before flags 0 3 2 0 1 0 0 0
before times 3 0 2 0 1 0 0
after flags  6 3 2 4 1 2 0 0
after times  3 6 2 4 1 2 0

The capacity rule: 2K+1, and the refusal

A Pleroma with key capacity K stores exactly 2K+1 harmonics per key line. Any store of K or fewer keys is decoded exactly, by Berlekamp-Massey syndrome decoding as in Reed-Solomon codes. All K items are held at once in one 2K+1 entry array, and reading any face (flags, arrangements, times) gives exact counts for all of them.

Past capacity, decoding fails at K+1 keys and returns false instead of guessing, so the store never returns a wrong answer. Add keys below to see what the package returned for each number of distinct keys.

Capacity K = 4

TryKeys results recorded from the real store for 0 to 9 distinct keys.

TryKeys result for 1 to 9 distinct keysWith key capacity 4, TryKeys decodes exactly up to 4 keys and refuses from 5 keys.123456789
What TryKeys returned for each number of keys
Key capacity 4: distinct keys added and the result of TryKeys
Distinct keysTryKeys returnedKeys decoded
0true0
1true1
2true2
3true3
4true4
5false0
6false0
7false0
8false0
9false0
Generated by running the published EvaluatedApplications.Phasor package (release 2.17.0). Every number is the package's own output.

Bind and Attend

store.Bind(other) binds every pair of items from two stores in one pass: keys add (mod the key space), flags XOR, arrangements compose, ticks add and counts multiply. The cost is one matrix product per order representation, not per pair of items.

Attend(query, face) reads three things from one contraction of the store for a flag predicate (an exact match, a partial match on a mask, or any Boolean function). Counts per value are the exact counts at each matched flag word, arrangement or tick. Shares are those counts divided by the total, summing to 1. Parity is the sign of the total. The cost is one spectrum and one inner product, whatever the number of items.

Bind with a one-item store
using Phasor;

var shape = new HologramShape { KeyCapacity = 8, FlagBits = 4, TimePeriod = 9 };
var store = new Pleroma(shape);
store.Add(new HologramItem(Key: 10, Flags: 0b0011, Time: 2), 3);
store.Add(new HologramItem(Key: 20, Flags: 0b0111, Time: 5), 1);

// Bind with a one-item store: every item moves by the same key, flags and time shift.
var shift = new Pleroma(shape);
shift.Add(new HologramItem(Key: 1, Flags: 0b0001, Time: 1));
store.Bind(shift);

if (store.TryItems(out var items))
    foreach (var (item, count) in items)
        Console.WriteLine($"{item.Key}: flags {item.Flags}, time {item.Time}, count {count}");
Output
11: flags 2, time 3, count 3
21: flags 6, time 6, count 1

Keys, bit maps and exact checks

Shift, scale and combine keys
ShiftKeys(k) adds k to every key in place. ScaleKeys(u) multiplies every key by a unit, or gathers several keys to one for a non-unit. CombineCycles(a, b) joins two stores on coprime key cycles by the Chinese remainder theorem. Scaling and combining need the optional CompleteKeys configuration.
Frobenius and shift registers
Frobenius(modulus, steps) squares every flag word as a polynomial over GF(2), and ShiftRegister(polynomial, steps) steps every word through a linear shift register, each exactly and in one pass.
Exact repair and redundancy
ReservedKeys lets Verify detect and Repair rebuild up to r lost or corrupted key-line harmonics. CheckPrime mirrors every cell in a second prime so VerifyCheck detects any corruption of one copy. PleromaParity keeps the exact sum of a group of stores and rebuilds any one lost store.
Dense and sparse pages
With CompleteKeys, a store is a dense page of up to 4,096 slots where Count and Counts read every slot exactly in one transform. PleromaSparsePage holds exact counts over keys anywhere in a huge key set in memory proportional to the keys present.

Built on the Pleroma

The HoloDb holographic plane uses the Pleroma as its data store. COUNT, SUM, MIN, MAX, GROUP BY, HAVING, COUNT DISTINCT, WHERE, JOIN and any Boolean predicate are exact on it.

Prior art

Reed-Solomon and BCH codes
Syndrome decoding (Reed and Solomon 1960, Berlekamp 1968, Massey 1969).
Berlekamp-Massey
The algorithm for finding minimal polynomials that the key decode uses.
PinSketch and minisketch
Set sketches built on the same construction (Talbot and others 2012, Poinsot and others 2017).
Holographic reduced representations
Plate's 1995 representation and its phase refinement, the approximate store the Pleroma is compared with.