Perplexity
Perplexity develops AI tools for search, browsing, research, content creation, organization, and workflow automation, including perplexity.ai, Comet, and Computer.
A Deterministic Polynomial-Time Algorithm Factors Polynomials Over Prime Fields
An OpenAI preprint claims a deterministic algorithm for factoring polynomials over prime fields in time polynomial in the degree and the bit length of the prime, without randomness or an integer-factorization oracle. Its central step is to construct labels that distinguish roots the algorithm cannot see, then use a greatest common divisor to turn that distinction into a factor. The paper handles even-sized root sets by counting and odd-sized sets through divisor classes on curves; its unconditional complexity claim also relies on a zero-free theorem proved in a separate companion manuscript.
A Three-Dimensional Tile Exists Without Any Fully Periodic Tiling
An OpenAI manuscript argues that a finite tile can cover the three-dimensional integer lattice by translations while admitting no fully periodic tiling. It builds the example from an arithmetic array that satisfies specified line constraints but cannot repeat vertically, then encodes those constraints in a tile so that any fully periodic spatial tiling would imply a forbidden period in the array.
Every Regular Language Has Generalized Star Height At Most Three
An OpenAI preprint, *Generalized Star Height at Most Three*, claims that every regular language over a finite alphabet can be described by a generalized regular expression with at most three nested Kleene stars, allowing complement as well as the usual operations. Its proof reorganizes finite-state computations into uniquely delimited episodes and applies two rounds of splitting; affine corrections help make the pieces independently checkable and can then be removed. The bound is a ceiling, not a claim that three layers are always needed.
One-Tape Computations Can Be Simulated in Two-Fifths-Power Space
An OpenAI preprint argues that a fixed deterministic machine with one writable tape, running for at most \(T\) steps, can be simulated in roughly \(T^{2/5}\) space, up to polylogarithmic factors. The bound improves on the square-root exponent for this setting, but the simulator may use vastly more time and need only determine the machine’s state and whether it has halted—not reproduce its final tape. The proof gets the space reduction by checking and recomputing local portions of the run rather than storing its full history.
The Standard Map Has Positive Metric Entropy at Sufficiently Large Parameters
An OpenAI preprint claims that the standard map has positive metric entropy with respect to normalized area for every sufficiently large positive parameter. The theorem means the largest Lyapunov exponent is positive on a set of positive area; it does not claim positivity almost everywhere or give a numerical threshold. The proof controls how stretching can cancel across intervals, then uses those bounds across doubling time scales to rule out zero exponent almost everywhere at arbitrarily large parameters.
Weakly Reversible Networks Share Eventual Bounds Within Each Stoichiometric Class
The OpenAI preprint *Uniform Permanence in Weakly Reversible Mass-Action Systems* claims that, for a finite weakly reversible network with fixed positive rate constants, every positive trajectory in a given stoichiometric class eventually enters the same compact region and remains there. The shared bounds depend on the network, rates and class—not on the initial state—but the time to reach them can vary without a uniform limit. The result establishes eventual bounds on concentrations, not convergence to a common equilibrium.
Two Limit Cycles Are the Exact Maximum for a Quintic Liénard Class
An OpenAI manuscript proves that a planar Liénard system with restoring force \(x\) and a polynomial damping term of degree at most four can have no more than two isolated periodic orbits, even when degenerate cycles are counted. The result applies to systems whose defining polynomial \(F\) has degree at most five, not to all planar systems with quintic terms. The authors establish the upper bound by comparing orbit halves and counting zeros of a matching function, then construct a small perturbation with two isolated cycles to show the bound is sharp.
Exact Measurements Still Require Many Samples Under Tight Memory
An OpenAI preprint proves a sample lower bound for recovering a direction from exact Gaussian linear measurements when a streaming learner’s memory is limited. In the specified finite-state model, any learner achieving average angular error at most \(\varepsilon\) with probability at least two-thirds needs at least \(c d\log(1/\varepsilon)/(1+M/d^2)\) observations, for an absolute constant \(c\) and sufficiently large dimension. The paper develops three proof routes, using projection moments, positive-cap domination and Riesz estimates to control how signal mass can concentrate across memory states.
Every Regular Language Has Generalized Star Height At Most Four
An OpenAI preprint claims that every regular language over a finite alphabet can be expressed using union, concatenation, complement and repetition with generalized star height at most four. The bound is uniform: it does not depend on the size of an automaton recognizing the language, and it limits nesting of repetition rather than the length of the expression. The proof converts an automaton into a finite monoid and builds shallow expressions by controlling how monoid products are recognized across cuts in a word.
Existential–Universal Real Sentences Fall Within a Fixed Counting Level
An OpenAI preprint argues that sentences asking whether one real tuple makes a polynomial condition true for every other real tuple can be decided within a fixed level of the counting hierarchy. The result applies to polynomial conditions represented by arithmetic circuits and allows arbitrarily many variables in both quantified blocks; it does not specify a numerical level for this two-block problem or claim a practical algorithm. The proof turns the universal challenge into a question about whether polynomial fibers contain real zeros, then encodes the existence of a uniformly good choice through finite algebraic tests.
A Uniform Decoder Reconstructs Strings From Randomly Deleted Traces
An OpenAI preprint on trace reconstruction claims a uniform algorithm that recovers any binary string of known length from independent deletion traces, with quasipolynomial sample and computation bounds for each fixed retention probability. When the empirical moments are sufficiently accurate, the algorithm’s tests exclude a wrong prefix and allow the correct extension to pass with strict slack; the paper claims this yields recovery with probability at least two-thirds. The guarantee is asymptotic, not a claim of practical speed.
A Full Band of Grazing Billiard Trajectories Forces Elliptic Tables
The preprint *Continuous Phase Foliations Create Analytic Caustic Collars* argues that a complete band of invariant billiard states near grazing motion forces a smooth, strictly convex planar table to be an ellipse. Its proof turns the foliation into exact action identities, uses them to establish analytic caustics near the boundary, and then applies a companion theorem to obtain rigidity. The hypothesis requires leaves throughout the band; isolated invariant curves or families with gaps do not meet it.
Identifying a Graph by Weisfeiler–Leman Refinement Is EXPTIME-Complete
An OpenAI preprint argues that deciding whether Weisfeiler–Leman refinement uniquely identifies a graph is EXPTIME-complete. That is a stronger question than whether refinement can distinguish a graph from one particular rival: identification requires ruling out every non-isomorphic graph with the same fingerprint. The result remains EXPTIME-complete when the refinement dimension is written in unary, according to the paper, which Perplexity Computer adapted into an animated explainer.
Parity Lifts Make Weisfeiler–Leman Refinement Detect Compatible Choices
An OpenAI manuscript argues that parity lifts turn a finite compatibility problem into a test of Weisfeiler–Leman refinement: a compatible choice makes two constructed graphs distinguishable, while its absence leaves them equivalent for every dimension \(k \ge 4\). The construction also links refinement distinguishability to bounded-treewidth witnesses, and uses the reduction to derive a conditional lower bound on the cost of computing WL histograms under positive-rate ETH.
Triple Ergodic Averages Converge to a Product of Means
An OpenAI preprint claims that for any three distinct, nonzero integer slopes, averages of three bounded measurable functions along the same orbit of an invertible, probability-preserving mixing system converge almost everywhere to the product of their means. The result holds along every positive integer length, not only along a selected subsequence. Coefficient identities let the authors extend the argument beyond equally spaced slopes, while analytic estimates control oscillation and establish convergence.
Every Regular Language Has Generalized Star-Height At Most 13
An OpenAI preprint claims that every regular language over a finite alphabet can be described, using complement as well as the usual regular-expression operations, with nested-star depth no greater than 13. The bound concerns nesting, not expression length, and does not show that 13 is necessary or resolve whether depth one always suffices. Perplexity Computer’s animated adaptation outlines the proof’s route through finite monoids, prediction trials and a sequence of shallow-depth constructions.
Matching Matrices Have Exponential PSD Rank Below the Unit Shift
An OpenAI preprint proves that adding any fixed shift strictly between zero and one to a matching matrix removes its zero entries but does not make it admit a small exact semidefinite representation: its positive semidefinite rank remains exponential in the number of vertices. The authors establish the lower bound for arbitrary positive semidefinite factors, then contrast it with the shift of one, where a diagonal construction gives a representation of polynomial size.
Weak Reversibility Prevents Extinction and Runaway Growth in Mass-Action Networks
An OpenAI preprint proves that, for finite weakly reversible reaction networks with mass-action kinetics, every trajectory starting at positive concentrations remains bounded above and bounded away from zero for all future time. The authors use a concave function to construct a region that traps each trajectory. The bounds may depend on the initial concentrations; the result does not establish convergence to equilibrium or a common bound for an entire compatibility class.
Weak Mixing Holds for Triangular Billiards With an Irrational Angle
An October 2026 OpenAI manuscript proves that the billiard flow in any non-degenerate triangle with an angle that is an irrational multiple of π is weak mixing. The result concerns the full system of positions and directions: the authors show that it has no nonconstant eigenfunctions, or hidden fixed-frequency clocks, which would obstruct weak mixing. An animated adaptation by Perplexity Computer illustrates the proof, whose central step is establishing enough regularity to rule out those eigenfunctions.
Self-Similar Measure Dimension Is Set by Distinct-Map Entropy
An OpenAI manuscript on self-similar measures on the line argues that Hausdorff dimension is determined not by the entropy of the choices used to generate a point, but by the information that survives after histories producing the same affine map are merged. It gives the dimension as the smaller of one and the rate of that map information divided by the average contraction rate, including cases with unequal or orientation-reversing contractions.
A Zero-Entropy System Has No Smooth Positive-Volume Model in Any Dimension
An OpenAI preprint constructs an ergodic, invertible, probability-preserving system with zero entropy that has no smooth model preserving a positive smooth volume density in any finite dimension. The authors’ argument turns on a mismatch: smooth dynamics would allow orbit pasts and futures to be spliced, while the system’s nested symbolic constraints force those halves to remain aligned. Zero information production per step, the paper shows, does not guarantee a smooth representation.
Mixing Alone Yields Pointwise Convergence for Fourfold Ergodic Averages
An OpenAI preprint claims that for a mixing, measure-preserving transformation, fourfold ergodic averages converge almost everywhere to the product of the four functions’ integrals, without requiring a mixing rate. Its proof addresses the gap between convergence at each fixed averaging length and convergence across all late lengths at an individual starting point: a point-dependent choice of a bad length can undermine independence. The manuscript uses tensor-packing bounds and a correlation argument to rule out persistent pointwise failure.
A 16-Million-Cylinder Cover Falls Below the Half-Area Bound
An OpenAI preprint gives a finite cover of a regular tetrahedron by angular cylinders whose total projected area is strictly less than half its minimum orthogonal shadow area. The margin is exceptionally small: the stated example uses 16 million cylinders and improves the normalized cost by just over 5 × 10⁻¹⁰. The authors’ proof establishes both complete coverage, including the boundary, and that the area saving exceeds the cost of the adjustments needed to make the cover work.
Edit Distance Requires Exponential Distortion in L₁ Embeddings
An OpenAI preprint argues that edit distance on words of length at most \(D\) cannot be embedded into \(L₁\) with low distortion: the best possible distortion grows as \(\exp(\Theta(\sqrt{\log D\,\log\log D}))\). The authors establish the lower bound using circle-based constructions, including a result that already holds for binary words of one fixed length, and give a matching-scale upper bound using overlapping substring histograms. The bounds match asymptotically, not in their constants.