Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDefinability of linear equation systems over groups and rings
219
0
0.0
(
0
)
Added by
Bjarki Holm
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Anuj Dawar
Ask ChatGPT about the research
No Arabic abstract
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are decidable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields. Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that all solvability problems for linear equation systems that separate fixed-point logic with counting from PTIME can be reduced to solvability over commutative rings. Moreover, we prove closure properties for classes of queries that reduce to solvability over rings, which provides normal forms for logics extended with solvability operators. We conclude by studying the extent to which fixed-point logic with counting can express problems in linear algebra over finite commutative rings, generalising known results on the logical definability of linear-algebraic problems over finite fields.
rate research
Read More
Let $k,pin mathbb{N}$ with $p$ prime and let $finmathbb{Z}[x_1,x_2]$ be a bivariate polynomial with degree $d$ and all coefficients of absolute value at most $p^k$. Suppose also that $f$ is variable separated, i.e., $f=g_1+g_2$ for $g_iinmathbb{Z}[x_i]$. We give the first algorithm, with complexity sub-linear in $p$, to count the number of roots of $f$ over $mathbb{Z}$ mod $p^k$ for arbitrary $k$: Our Las Vegas randomized algorithm works in time $(dklog p)^{O(1)}sqrt{p}$, and admits a quantum version for smooth curves working in time $(dlog p)^{O(1)}k$. Save for some subtleties concerning non-isolated singularities, our techniques generalize to counting roots of polynomials in $mathbb{Z}[x_1,ldots,x_n]$ over $mathbb{Z}$ mod $p^k$. Our techniques are a first step toward efficient point counting for varieties over Galois rings (which is relevant to error correcting codes over higher-dimensional varieties), and also imply new speed-ups for computing Igusa zeta functions of curves. The latter zeta functions are fundamental in arithmetic geometry.
We construct, for any finite commutative ring $R$, a family of representations of the general linear group $mathrm{GL}_n(R)$ whose intertwining properties mirror those of the principal series for $mathrm{GL}_n$ over a finite field.
For a commutative ring R with many units, we describe the kernel of H_3(inc): H_3(GL_2(R), Z) --> H_3(GL_3(R), Z). Moreover we show that the elements of this kernel are of order at most two. As an application we study the indecomposable part of K_3(R).
In this paper we extend and prove in detail the Finite Rank Theorem for connection matrices of graph parameters definable in Monadic Second Order Logic with counting (CMSOL) from B. Godlin, T. Kotek and J.A. Makowsky (2008) and J.A. Makowsky (2009). We demonstrate its vast applicability in simplifying known and new non-definability results of graph properties and finding new non-definability results for graph parameters. We also prove a Feferman-Vaught Theorem for the logic CFOL, First Order Logic with the modular counting quantifiers.
The aim of this paper is to introduce and study Lie algebras and Lie groups over noncommutative rings. For any Lie algebra $gg$ sitting inside an associative algebra $A$ and any associative algebra $FF$ we introduce and study the algebra $(gg,A)(FF)$, which is the Lie subalgebra of $FF otimes A$ generated by $FF otimes gg$. In many examples $A$ is the universal enveloping algebra of $gg$. Our description of the algebra $(gg,A)(FF)$ has a striking resemblance to the commutator expansions of $FF$ used by M. Kapranov in his approach to noncommutative geometry. To each algebra $(gg, A)(FF)$ we associate a ``noncommutative algebraic group which naturally acts on $(gg,A)(FF)$ by conjugations and conclude the paper with some examples of such groups.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
