Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [algebra]

The tag has no usage guidance.

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16
votes
0answers
359 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 ...
9
votes
0answers
100 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 ...
9
votes
0answers
284 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 ...
7
votes
0answers
56 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,...
7
votes
0answers
173 views

Complete axiomatization of relation algebras without ${}^-$ and $\top$

I'm working on a more thorough algebraic treatment of delta modeling. Briefly, deltas are syntactic entities that can modify products (as in 'software products'). They actually represent relations on ...
5
votes
0answers
109 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....
5
votes
0answers
71 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 ...
4
votes
0answers
83 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. ...
4
votes
1answer
216 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 ...
3
votes
0answers
75 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}]...
2
votes
0answers
102 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
votes
0answers
68 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 ...
2
votes
0answers
113 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 ...
2
votes
0answers
73 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 ...
2
votes
0answers
136 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
vote
0answers
20 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 ...
1
vote
0answers
59 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\}$ ...
1
vote
0answers
88 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 ...
1
vote
0answers
115 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 ...
1
vote
0answers
62 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 ...
1
vote
0answers
40 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 ...
1
vote
0answers
89 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
vote
0answers
116 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
vote
0answers
102 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 ...
0
votes
0answers
120 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 ...
0
votes
0answers
336 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 \...