Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Algebra

175 missions · 96 completed

The study of algebraic structures — groups, rings, and fields — and, through algebraic geometry, the geometry of the solution sets of polynomial equations. Using commutative algebra to describe these varieties, the field provides a common language of symmetry and structure that underlies much of modern mathematics.

Missions

Open79Completed96All175
CombinatoricsDiscrete Geometry·Captain: mikedeng1

A Large Family of Maximum Scattered Linear Sets of PG(1, q^n) and Their Associated MRD Codes 1: For q Odd, t ≥ 3, h ∉ 𝔽_{q^t} and h^(q^t+1) = −1, ψ_{h,t} Is Scattered over 𝔽_{q^{2t}}Research Paper

A linear set of a projective space over a finite field is the set of points spanned by the nonzero vectors of a subspace over a subfield. They have been used to construct and characterize semifields, rank-metric codes, translation spreads, translation ovoids, two-intersection sets and the blocking sets for which Lunardon introduced them (Polverino 2010;…

13 thms3 active usersReviewed
Group TheoryNumber Theory·Captain: LG

The Inverse Galois ProblemOpen Problem

Galois theory attaches to every finite Galois extension L/KL/KL/K a finite group Gal(L/K)\mathrm{Gal}(L/K)Gal(L/K), the group of field automorphisms of LLL fixing KKK pointwise, and the fundamental theorem of Galois theory turns the subfield structure of L/KL/KL/K into the subgroup structure of that group. The inverse Galois problem asks whether this correspondence is surjective over the…

22 thms3 active usersReviewed
Group TheoryRepresentation Theory·Captain: LG

Group Cohomology and the Classification of ppp-Groups with a Cyclic Subgroup of Index pppResearch Paper

Group cohomology assigns to a group GGG and a GGG-module AAA a sequence of abelian groups Hn(G,A)H^n(G,A)Hn(G,A) that measure how far GGG-equivariant constructions are from being split. In low degrees these groups classify concrete algebraic objects: H1(G,A)H^1(G,A)H1(G,A) parametrizes crossed homomorphisms modulo principal ones, and H2(G,A)H^2(G,A)H2(G,A) parametrizes equivalence classes of extensions of GGG…

14 thms2 active usersReviewed
Computational ComplexityLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Partial Homogenization and the Structure of Optimal Algebraic AlgorithmsResearch Paper

A quadratic map ϕ=(ϕ1,…,ϕK)\phi=(\phi_1,\dots,\phi_K)ϕ=(ϕ1​,…,ϕK​) is a tuple of quadratic forms in variables z=(z1,…,zN)z=(z_1,\dots,z_N)z=(z1​,…,zN​). Polynomial multiplication, matrix multiplication and multiplication in an algebra such as C\mathbb CC over R\mathbb RR are all quadratic maps. Algebraic complexity theory measures how many multiplications such a map needs, and the classical count is the…

15 thms2 active usersReviewed
Complexity Theory·Captain: Shuze Chen

A Dichotomy for Complex Boolean Holant with Binary DisequalityResearch Paper

Many counting problems ask for a sum, over all assignments of bits, of a product of local weights. A complexity dichotomy sorts every choice of local weights into two classes: those for which the sum can be computed in polynomial time, and those for which computing it is #P-hard. For Boolean counting constraint satisfaction such dichotomies are known for…

30 thms2 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: iris

A Circuit Complexity Trichotomy For Regular LanguagesResearch Paper

Unbounded fan-in Boolean circuits are the standard model of parallel computation, and finite automata the standard model of sequential computation with constant memory. Regular languages sit where the two meet: they separate AC0\mathsf{AC}^0AC0 from NC1\mathsf{NC}^1NC1 (Furst, Saxe, Sipser 1984), any separation of ACC0\mathsf{ACC}^0ACC0 or TC0\mathsf{TC}^0TC0 from NC1\mathsf{NC}^1NC1 is…

51 thms2 active usersReviewed
cryptographyTheoretical Computer Science·Captain: iris

Counterexamples to Beyond-Johnson Proximity Gaps over Binary FieldsResearch Paper

Hash-based succinct proof systems (SNARKs) check that committed words are close to a Reed–Solomon code by querying a few entries of a random combination f+zgf+zgf+zg of two words. Their soundness rests on proximity gaps: if f+zgf+zgf+zg agrees with a codeword on many positions, then fff and ggg agree with codewords on many common positions, except for a small set of challenges …

28 thms2 active usersReviewed
CombinatoricscryptographyInformation Theory+1·Captain: Shuze Chen

Mutual Correlated Agreement and List-Decoding: Improvements and SeparationsResearch Paper

Interactive oracle proofs (IOPs) for proximity to Reed–Solomon and other linear codes, the engine of hash-based succinct arguments such as FRI, STIR and WHIR, repeatedly fold several words into one random linear combination and test only the combination. Soundness needs a guarantee in the other direction: if the combined word is close to the code, the input…

17 thms2 active usersReviewed
Algebraic GeometryComputational ComplexityInformation Theory·Captain: Shuze Chen

Quasilinear Encoding at the Quadratic Alphabet Scale via Short Cartier BasesResearch Paper

A linear code over a finite field FQ\mathbb F_QFQ​ encodes KKK message symbols as NNN codeword symbols; its minimum distance ddd guarantees recovery from ttt errors and eee erasures whenever 2t+e<d2t+e<d2t+e<d. The Singleton bound gives d≤N−K+1d\le N-K+1d≤N−K+1. For a target gap 0<ε<10<\varepsilon<10<ε<1 one asks for codes with

19 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

A Dichotomy Theorem for CSP-Based Ideal MembershipResearch Paper

The ideal membership problem asks whether a polynomial f0f_0f0​ lies in the ideal generated by given polynomials. Constraint satisfaction gives a natural family of instances: over a finite domain D⊆QD\subseteq\mathbb QD⊆Q, the domain and the constraints of a CSP instance PPP are polynomial equations, and they generate a radical ideal I(P)I(P)I(P) consisting exactly of the…

31 thms2 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: Shuze Chen

Deterministic Algorithms for Low Individual Degree Factors of Sparse PolynomialsResearch Paper

Factoring multivariate polynomials is a basic task of computer algebra. For polynomials given by circuits or as black boxes it has efficient randomized algorithms (Kaltofen; Kaltofen–Trager), surveyed in §1 of the source, but no deterministic one is known even for sparse polynomials, those with few monomials. Derandomizing factorization is tied to…

23 thms2 active usersReviewed
Computational ComplexityLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Hitting Sets for Polynomials with Small Hasse Derivative Space over Arbitrary Characteristic FieldsResearch Paper

Polynomial identity testing (PIT) asks whether a polynomial given by an algebraic circuit is the zero polynomial. In the blackbox setting the circuit can only be evaluated. A hitting set supplies a fixed family of queries that detects every nonzero polynomial in the class. A standard way to do so is a hitting set generator: a low-degree polynomial map GGG in…

24 thms2 active usersReviewed
Computational ComplexityTheoretical Computer Science·Captain: Shuze Chen

Uniform Subpower Membership for Finite Mal'tsev AlgebrasResearch Paper

A finite algebra AAA is a finite set with finitely many operations. Given tuples g1,…,gm∈Ang^1, \dots, g^m \in A^ng1,…,gm∈An, the subpower membership problem asks whether a target tuple can be obtained from them by applying the operations of AAA coordinatewise, any number of times. The set of obtainable tuples, Sg(G)\mathrm{Sg}(G)Sg(G), can have exponentially many elements in nnn, so the…

13 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Optimal Quantum Query Bounds for Identifying Classes of 333-TensorsResearch Paper

Identifying an unknown function from a known class by querying it is the exact-learning or interpolation problem, and for polynomials over a finite field it is the query side of black-box identity testing. By counting, no classical algorithm, even a randomized one, identifies a member of a class C\mathcal CC of functions over Fq\mathbb F_qFq​ with fewer than …

51 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

An Algebraic Polynomial Evaluation Datastructure for Fields of Large CharacteristicResearch Paper

A polynomial evaluation datastructure stores a precomputed encoding of a multivariate polynomial so that the polynomial can be evaluated at any point by reading only a few cells of the encoding. Such structures were introduced for univariate polynomials in the cell-probe literature (Miltersen 1995) and were developed for multivariate polynomials as a tool…

18 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

The quantum query complexity of the semigroup product problemResearch Paper

Many quantum query problems are iterated products in disguise. Membership in a regular language reduces to computing the product x1x2⋯xnx_1x_2\cdots x_nx1​x2​⋯xn​ of input letters in a finite monoid and testing whether it lies in an accepting set. Maximum finding is a product in the monoid (N,max⁡)(\mathbb N,\max)(N,max), and finding all distinct letters of an input is a product in the…

50 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Approximating Transcendence Degree in Medium CharacteristicResearch Paper

Deciding whether polynomials f1,…,fm∈F[x1,…,xn]f_1,\dots,f_m\in\mathbb F[x_1,\dots,x_n]f1​,…,fm​∈F[x1​,…,xn​] satisfy a polynomial relation, and computing their transcendence degree, is a basic problem in algebraic complexity theory. It underlies algebraic independence testing and rank extractors for polynomial sources (Dvir, Gabizon, Wigderson 2009), and the Jacobian is the standard tool for…

22 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Faster Power Series Composition in Fixed Positive CharacteristicResearch Paper

Truncated power series composition asks, given the coefficients of an outer polynomial f(y)=∑i<mfiyif(y)=\sum_{i<m}f_iy^if(y)=∑i<m​fi​yi and an inner polynomial g(x)=∑j<ngjxjg(x)=\sum_{j<n}g_jx^jg(x)=∑j<n​gj​xj over a commutative ring RRR, for the first nnn coefficients of f(g(x))f(g(x))f(g(x)). It is a basic operation of computer algebra: with f=F mod ynf=F\bmod y^nf=Fmodyn and g=G mod xng=G\bmod x^ng=Gmodxn for power series with G(0)=0G(0)=0G(0)=0 it computes F(G(x)) mod xnF(G(x))\bmod x^nF(G(x))modxn…

28 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Cube-Root Soundness Is Optimal for the Line–versus–Point TestResearch Paper

The Reed–Muller code RMq(m,d)\mathrm{RM}_q(m,d)RMq​(m,d) consists of the evaluation tables of polynomials Q∈Fq[X1,…,Xm]Q\in\mathbb F_q[X_1,\dots,X_m]Q∈Fq​[X1​,…,Xm​] of total degree at most ddd. Restricted to an affine line, such a polynomial becomes a univariate polynomial of degree at most ddd. The line–versus–point test checks exactly this local property. It is a two-query consistency test: given a…

29 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Unbounded Fan-in Circuits and Associative Functions: A Finite Semigroup Has Constant-Depth, Polynomial-Size Circuits Exactly When It Is GroupfreeResearch Paper

Constant-depth circuits with unbounded fan-in are the standard model of very fast parallel computation with cheap wide gates. The lower bound of Furst, Saxe and Sipser (1984, doi:10.1007/BF01744431) shows that parity is out of reach at polynomial size, and later work sharpened it, notably Håstad (1986, doi:10.1145/12130.12132). On the other side, binary…

16 thms2 active usersReviewed
Complexity Theory·Captain: arpcs

Ordinary binary polynomial multiplication below nlog⁡nn\log nnlognResearch Paper

Polynomial multiplication is a basic operation in computer algebra: two coefficient lists must be converted into the coefficient list of their product. Its bit complexity depends on the coefficient field and the permitted machine operations. For a field fixed before the input length varies, Harvey and van der Hoeven established the unconditional benchmark …

4 thms2 active usersReviewed
CombinatoricsRepresentation Theory·Captain: mikedeng1

Supersymmetric Polynomials and the Center of the Walled Brauer Algebra: When B_{r,s}(δ) Is Semisimple, Supersymmetric Polynomials in the Jucys–Murphy Elements Generate Its CenterResearch Paper

The walled Brauer algebra Br,s(δ)B_{r,s}(\delta)Br,s​(δ) is the centralizer algebra of mixed Schur–Weyl duality: for δ=n\delta=nδ=n it acts on the mixed tensor space V⊗r⊗(V∗)⊗sV^{\otimes r}\otimes (V^*)^{\otimes s}V⊗r⊗(V∗)⊗s of V=CnV=\mathbb C^nV=Cn and commutes with gln\mathfrak{gl}_ngln​, and for δ=m−n\delta=m-nδ=m−n it plays the same role for the general linear supergroup GL(m∣n)GL(m|n)GL(m∣n). Its representation theory has been…

21 thms2 active usersReviewed
Mathematical Physics·Captain: mikedeng1

Continuum Limit of gl(M|N) Spin Chains: For an Odd Sourceless Simple Root, gl(M|N) Bethe Ansatz Solutions with Identified Neighbour Roots Are Exactly Lifts of gl(M−1|N−1) Solutions of Equal EnergyResearch Paper

Integrable spin chains with a Lie superalgebra symmetry gl(M∣N)\mathfrak{gl}(M|N)gl(M∣N) are lattice regularizations of two-dimensional field theories with target-space supersymmetry, such as the gl(M∣N)\mathfrak{gl}(M|N)gl(M∣N) Gross–Neveu models and sigma models on superspaces, which appear in the study of disordered systems, polymers and the AdS/CFT correspondence. Their spectra…

7 thms2 active usersReviewed
Algebraic GeometryGroup Theory·Captain: mikedeng1

Observable actions of algebraic groups: a reductive action is observable iff some closed orbit has maximal dimension, and the socle is the largest observable closed subsetResearch Paper

An action of an affine algebraic group GGG on an affine variety XXX is observable when invariant regular functions see every nonzero GGG-stable ideal of the coordinate ring: if I⊆k[X]I\subseteq k[X]I⊆k[X] is a nonzero GGG-stable ideal, then IG≠(0)I^G\neq(0)IG=(0). The notion goes back to Grosshans' theory of observable subgroups (F. D. Grosshans, Observable groups and Hilbert's fourteenth…

10 thms2 active usersReviewed
CombinatoricsRepresentation Theory·Captain: mikedeng1

On Central Idempotents in the Brauer Algebra: The Equation uX = −u Is Uniquely Solvable in Orbit Sums with Coefficients in K, and 1 + X Is the Splitting Idempotent of J_n(ℓ)Research Paper

The Brauer algebra packages pairings of points into an algebra whose multiplication records how pairings join when diagrams are stacked. It was introduced by Brauer as the centralizer algebra of orthogonal and symplectic groups acting on tensor powers of their natural representation (Brauer 1937), and is semisimple for generic δ\deltaδ (Wenzl 1988). It…

8 thms2 active usersReviewed
PreviousPage 2 of 4Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me