More Like this

1. On n -dependent groups and fields II

   https://doi.org/10.1017/fms.2021.35  

   Chernikov, Artem; Hempel, Nadja (January 2021, Forum of Mathematics, Sigma)

   null (Ed.)

   Abstract We continue the study of n -dependent groups, fields and related structures, largely motivated by the conjecture that every n -dependent field is dependent. We provide evidence toward this conjecture by showing that every infinite n -dependent valued field of positive characteristic is henselian, obtaining a variant of Shelah’s Henselianity Conjecture in this case and generalizing a recent result of Johnson for dependent fields. Additionally, we prove a result on intersections of type-definable connected components over generic sets of parameters in n -dependent groups, generalizing Shelah’s absoluteness of $$G^{00}$$ in dependent theories and relative absoluteness of $$G^{00}$$ in $$2$$ -dependent theories. In an effort to clarify the scope of this conjecture, we provide new examples of strictly $$2$$ -dependent fields with additional structure, showing that Granger’s examples of non-degenerate bilinear forms over dependent fields are $$2$$ -dependent. Along the way, we obtain some purely model-theoretic results of independent interest: we show that n -dependence is witnessed by formulas with all but one variable singletons; provide a type-counting criterion for $$2$$ -dependence and use it to deduce $$2$$ -dependence for compositions of dependent relations with arbitrary binary functions (the Composition Lemma); and show that an expansion of a geometric theory T by a generic predicate is dependent if and only if it is n -dependent for some n , if and only if the algebraic closure in T is disintegrated. An appendix by Martin Bays provides an explicit isomorphism in the Kaplan-Scanlon-Wagner theorem. 

   more » « less
2. Counting mod n in pseudofinite fields

   https://doi.org/10.1007/s11856-021-2279-x  

   Johnson, Will (January 2021, Israel Journal of Mathematics)

   We show that in an ultraproduct of finite fields, the mod-n nonstandard size of definable sets varies definably in families. Moreover, if K is any pseudofinite field, then one can assign "nonstandard sizes mod n" to definable sets in K. As n varies, these nonstandard sizes assemble into a definable strong Euler characteristic on K, taking values in the profinite completion hat(Z) of the integers. The strong Euler characteristic is not canonical, but depends on the choice of a nonstandard Frobenius. When Abs(K) is finite, the Euler characteristic has some funny properties for two choices of the nonstandard Frobenius. Additionally, we show that the theory of finite fields remains decidable when first-order logic is expanded with parity quantifiers. However, the proof depends on a computational algebraic geometry statement whose proof is deferred to a later paper. 

   more » « less
3. Definable structures on flat bundles

   https://doi.org/10.1112/blms.12879  

   Bakker, Benjamin; Mullane, Scott (July 2023, Bulletin of the London Mathematical Society)

   Abstract A flat vector bundle on an algebraic variety supports two natural definable structures given by the flat and algebraic coordinates. In this note, we show these two structures are compatible, subject to a condition on the local monodromy at infinity that is satisfied for all flat bundles underlying variations of Hodge structures. 

   more » « less
4. Computability in infinite Galois theory and algorithmically random algebraic fields

   https://doi.org/10.1112/jlms.70017  

   Calvert, Wesley; Harizanov, Valentina; Shlapentokh, Alexandra (November 2024, Journal of the London Mathematical Society)

   Abstract We introduce a notion of algorithmic randomness for algebraic fields. We prove the existence of a continuum of algebraic extensions of that are random according to our definition. We show that there are noncomputable algebraic fields which are not random. We also partially characterize the index set, relative to an oracle, of the set of random algebraic fields computable relative to that oracle. In order to carry out this investigation of randomness for fields, we develop computability in the context of the infinite Galois theory (where the relevant Galois groups are uncountable), including definitions of computable and computably enumerable Galois groups and computability of Haar measure on the Galois groups. 

   more » « less
5. Proof Complexity Lower Bounds from Algebraic Circuit Complexity

   https://doi.org/10.4086/toc.2021.v017a010  

   Forbes, Michael A.; Shpilka, Amir; Tzameret, Iddo; Wigderson, Avi (January 2021, Theory of Computing)

   Raz, Ran (Ed.)

   We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem. 

   more » « less