Questions tagged [algebra]
The algebra tag has no usage guidance.
31 questions with no upvoted or accepted answers
16
votes
0
answers
372
views
Looking for an operator on polynomials
I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder ...
- 11k
11
votes
0
answers
200
views
Are there cascade decompositions of machines that are more general than finite automata?
The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
- 361
9
votes
0
answers
304
views
What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?
$\mathsf{GNI}$ Private Coin
In [GMW85], the authors provided the famous interactive proof $\mathsf{IP}$ of Graph Non Isomorphism $\mathsf{GNI}$.
The $\mathsf{GNI}$ protocol entails a verifier ...
- 1,145
7
votes
0
answers
68
views
Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times
When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:
Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
- 71
6
votes
0
answers
240
views
Satisfiability and a Galois Theory Analog
Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows:
$$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$
where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
- 101
5
votes
0
answers
116
views
Algebraic dependence of roots of irreducibles over a finite field
I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math....
- 393
5
votes
0
answers
81
views
Finding of dimension of algebraic varieties
I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf).
Are ...
- 2,023
4
votes
0
answers
99
views
Residual for transitive hull
I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...
- 235
4
votes
1
answer
220
views
Optimizing multiplication in a partly commutative semigroup
Let us say I have a semigroup M and its basis B. I know which elements of B commute.
What is the most efficient way to do multiplication in such a semigroup?
Essentially, this is a question of how ...
- 9,011
3
votes
0
answers
57
views
Complexity of minimizing the index of a subgroup of the free group
Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
- 2,181
3
votes
0
answers
82
views
Finding degree two subfield
Let $K=\frac{\mathbb{Q}[x]}{<f(x)>}$ where $f(x)$ is irreducible over $\mathbb{Q}$ and has even degree. I want to find $K_2$ such that $ \mathbb{Q} \subseteq K_2\subseteq K$ and $[K_2:\mathbb{Q}]...
- 243
2
votes
0
answers
89
views
Multipoint evaluation in Lagrange basis
Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of ...
2
votes
0
answers
123
views
Relation between automorphism group of a linear code and its dual code
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.
In ...
- 387
2
votes
0
answers
136
views
On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits
As I understand from the survey "Progress on Polynomial Identity Testing - II"
a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.
However, there exists paper ...
- 2,023
2
votes
0
answers
72
views
Standard basis for recurrence relations
In polynomial algebra there is a powerful tool for treating system of polynomial equations. It is standard or Groebner Bases. It allows to verify if system is consistent, eliminate variables, reduce ...
user44741
2
votes
0
answers
121
views
Possible generalizations of associativity?
The well-known notion of associativity in algebra leads to structures with interesting properties, such as groups or semigroups. According to a paper by John Rhodes, some researchers in algebra and ...
- 21
2
votes
0
answers
76
views
Composition series and isogeny
I'm not sure this question is appropriate for this site, but it might have some connections with computational algebra.
Consider a fixed "category" $\sf{Cat}$ (in the sense of category theory, but ...
- 1,312
2
votes
0
answers
139
views
Extending the notion of independence
Background
I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered here but I couldn't find a satisfactory ...
- 1,312
1
vote
0
answers
27
views
Worst case polynomial in elimination theory under rank conditions?
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
- 13.3k
1
vote
0
answers
67
views
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
- 2,057
1
vote
0
answers
90
views
Counting points on curves
It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a ...
- 2,023
1
vote
0
answers
119
views
Computing $a^e \mod p^n$ Efficiently
It is well known that we can compute:
$$
a^e \mod m
$$
in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering ...
- 111
1
vote
0
answers
69
views
The curve used in Parvaresh-Vardy decoding
Consider the Parvaresh-Vardy list decoder.
As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of ...
- 393
1
vote
0
answers
46
views
Decoding of Gabidulin codes
Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
- 393
1
vote
0
answers
95
views
Restoring symmetry in certain combinatorial bijections?
I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an $n$...
- 1,312
1
vote
0
answers
123
views
Spectrum of a variety: a possible connection btw ordinals and structures?
Consider a variety of algebras $\mathbb{V} = \mathbb{V}(\sigma,\tau)$ which consists of the set of algebras defined over a fixed signature $\sigma$ and satisfying a set of identities $\tau$. We may ...
- 1,312
1
vote
0
answers
103
views
Equivalence relations on strongly regular graphs with same parameters
Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter
$(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set?
My motivation is to approach ...
- 1,311
0
votes
0
answers
58
views
Product types: algebraic structure for modeling product types with commutative and associative product operation
Is there a known algebraic structure over set of Types (however they are defined) which is equipped with:
commutative and associative product operation for building product types from simpler types, ...
0
votes
0
answers
75
views
Polynomial GCD exact complexity in terms of degree and number of variables
https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
- 13.3k
0
votes
0
answers
124
views
count number of i such that ( (a*i+b) mod p) mod k == l
How to determine the number of $i$'s as fast as possible such that
$$1\le i \le L$ and $((ai+b)\mod p) \mod k = l$$
where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$.
This ...
- 121
0
votes
0
answers
350
views
Commutation between a permutation matrix and the sum of permutation matrices corresponding to n-cycles
Let $S_n$ be the set of all permutations of $n$ elements. Consider the regular representation of $S_n$ in $GL(\mathbb{R}^{n!})$ by $S_n\ni \pi \rightarrow P_\pi$: $(P_\pi)_{\sigma\tau}=1$ if $\pi \...
- 795