5 ms·

But... what is a ring? What is a formal variable? What is a vector space? What does "algebra over the ring" mean? His point is the terms are dense too

agrounds 2mo ago
Absolutely agree. All formal statements (like mathematical ones) are going to have some level of assumed background. And as the assumed background expands, the language naturally becomes more information dense. As for your specific questions, I believe Wikipedia does a great job of answering two of them for a layperson: https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Vector_space https://en.wikipedia.org/wiki/Vector_space For the others, I’ll say that a formal variable is just a symbol (literally, like the letter t). With such a symbol, we can construct polynomials like 2t^2 - t + 3. Also, there’s no need to only use integers as the allowed coefficients; you can use any ring you like instead. An “algebra over the ring R” is what I was attempting to define in my comment above. The algebra is “over” R if we can multiply an element of the algebra by an element of R. The useful analogy here is scalar multiplication in a vector space: you can multiply a vector by 2 to double it or -1/2 to reflect and shorten it. More generally, it makes perfect sense to consider some more general version of vectors which can be scalar multiplied by elements of any ring R.
- ChrisClark 2mo ago
  My questions were mostly to agree it's hard to understand, but they were true ignorance. I'm glad you answered them. It finally makes sense to me, and now I realize I didn't even understand "over" in that context. That Ring wiki page though, um, nope... :D
  - agrounds 2mo ago
    > That Ring wiki page though, um, nope... :D Fair enough! At a super high level, a ring is just a collection that has a similar structure to what you’re used to “numbers” having. That is, you can add, subtract, and multiply them. Not divide! If we restrict ourselves to just whole numbers then 2/3 is not allowed. We also require that something like 0 and 1 have to be there. “Like zero” means 0 + x = x for every x in your collection, and “like one” means 1x = x for every x. And lastly, we require that the distributive property holds. Examples include the set of whole numbers (Z), the rationals aka fractions (Q), the reals (R), complex numbers (C). These are all infinite rings, but there are also finite rings such as the set of whole numbers modulo a fixed number n, denoted Z/nZ. For instance, Z/2Z has only two elements, namely 0 and 1, with rules like 1 + 1 = 0. There are also polynomial rings, like Z[t], whose elements are all polynomials with integer coefficients (e.g. 3t^3 - t - 2). You can add, subtract, and multiply such polynomials and the result is more polynomials, so this collection is indeed a ring.
- hexasquid 2mo ago
  Ah, t is a formal variable, a symbol, like the letter t. Not like a drink with jam and bread.
aleph_minus_one 2mo ago
> But... what is a ring? What is a formal variable? What is a vector space? What does "algebra over the ring" mean? All these terms were taught to computer science (and of course math, physics, ...) students as part of getting their degree in computer science, because these concepts are important for many algorithms.
- agrounds 2mo ago
  I studied a lot of abstract algebra in college and grad school and I’m surprised that rings and algebras would come up in a CS degree. What algorithms topics used those concepts? Something about polynomials?
  - ndriscoll 2mo ago
    (At least some) error-correcting codes are based on polynomials over finite fields. I couldn't say much more, but it's at least intuitively plausible since e.g. an nth degree polynomial is defined by any n+1 points, so if you know say n+1+p ("p" for "parity") points, you can lose up to p and still recover the polynomial.
  - aleph_minus_one 2mo ago
    Rings: * Determinant calculation: - The Samuelson–Berkowitz algorithm is best understood in terms of general rings - The Faddeev–LeVerrier algorithm and determinant calculation using Gaussian elimination work on rings with specific properties (for the Faddeev–LeVerrier algorithm the restriction is on the characteristic of the ring, for Gaussian elimination the ring must be an integral domain (ideally a field)). * Ring-learning with errors (for post-quantum cryptography and homomorphic cryptography). Here, a specific ring is the central object. * Number-Theoretic Transform (NTT): Basically a generalization of the Fourier Transform to the ring Z_n. Important for arbitrary-precision integer arithmetic * Chinese Remainder Theorem. Often only formulated for the ring Z, but it can be generalized to larger classes of rings. Used for example in Shamir’s scheme for secret sharing (cryptography) * The theory of BCH and Reed-Solomon codes uses a specific ring * The AKS Primality Test (a really deep result in computational number theory) uses the ring Z_n[X]/(x^r-1). --- Algebras: Very often, a ring is constructed from another ring. Examples: * the polynomial ring R[X_1, ..., X_n] * The ring of (square) matrices over a ring R So, using algebras in algorithms often means: "we want to make use use of this additional structure that our (more sophisticated) ring has)". (Associative) R-algebras formalize this concept of "ring with additional structure". To just give one algorithm for polynomials: * Buchberger algorithm for computing a Gröbner basis Other examples: * Clifford algebras for a lot of geometric problems (special case: quaternions (a 4-dimensional \mathbb{R}-algebra) for rotations in \mathbb{R}^3). * If you are willing to also consider semi-rings (in this case: tropical semi-rings): the Floyd-Warshall algorithm for finding shortest paths and the Viterbi algorithm for finding the most likely sequence of states in a Hidden-Markov Model (HMM) can very elegantly formulated using the matrix semiring over the tropical semiring.

agrounds 2mo ago

Absolutely agree. All formal statements (like mathematical ones) are going to have some level of assumed background. And as the assumed background expands, the language naturally becomes more information dense. As for your specific questions, I believe Wikipedia does a great job of answering two of them for a layperson: https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Vector_space https://en.wikipedia.org/wiki/Vector_space For the others, I’ll say that a formal variable is just a symbol (literally, like the letter t). With such a symbol, we can construct polynomials like 2t^2 - t + 3. Also, there’s no need to only use integers as the allowed coefficients; you can use any ring you like instead. An “algebra over the ring R” is what I was attempting to define in my comment above. The algebra is “over” R if we can multiply an element of the algebra by an element of R. The useful analogy here is scalar multiplication in a vector space: you can multiply a vector by 2 to double it or -1/2 to reflect and shorten it. More generally, it makes perfect sense to consider some more general version of vectors which can be scalar multiplied by elements of any ring R.

ChrisClark 2mo ago
My questions were mostly to agree it's hard to understand, but they were true ignorance. I'm glad you answered them. It finally makes sense to me, and now I realize I didn't even understand "over" in that context. That Ring wiki page though, um, nope... :D
- agrounds 2mo ago
  > That Ring wiki page though, um, nope... :D Fair enough! At a super high level, a ring is just a collection that has a similar structure to what you’re used to “numbers” having. That is, you can add, subtract, and multiply them. Not divide! If we restrict ourselves to just whole numbers then 2/3 is not allowed. We also require that something like 0 and 1 have to be there. “Like zero” means 0 + x = x for every x in your collection, and “like one” means 1x = x for every x. And lastly, we require that the distributive property holds. Examples include the set of whole numbers (Z), the rationals aka fractions (Q), the reals (R), complex numbers (C). These are all infinite rings, but there are also finite rings such as the set of whole numbers modulo a fixed number n, denoted Z/nZ. For instance, Z/2Z has only two elements, namely 0 and 1, with rules like 1 + 1 = 0. There are also polynomial rings, like Z[t], whose elements are all polynomials with integer coefficients (e.g. 3t^3 - t - 2). You can add, subtract, and multiply such polynomials and the result is more polynomials, so this collection is indeed a ring.
hexasquid 2mo ago
Ah, t is a formal variable, a symbol, like the letter t. Not like a drink with jam and bread.

aleph_minus_one 2mo ago

> But... what is a ring? What is a formal variable? What is a vector space? What does "algebra over the ring" mean? All these terms were taught to computer science (and of course math, physics, ...) students as part of getting their degree in computer science, because these concepts are important for many algorithms.

agrounds 2mo ago
I studied a lot of abstract algebra in college and grad school and I’m surprised that rings and algebras would come up in a CS degree. What algorithms topics used those concepts? Something about polynomials?
- ndriscoll 2mo ago
  (At least some) error-correcting codes are based on polynomials over finite fields. I couldn't say much more, but it's at least intuitively plausible since e.g. an nth degree polynomial is defined by any n+1 points, so if you know say n+1+p ("p" for "parity") points, you can lose up to p and still recover the polynomial.
- aleph_minus_one 2mo ago
  Rings: * Determinant calculation: - The Samuelson–Berkowitz algorithm is best understood in terms of general rings - The Faddeev–LeVerrier algorithm and determinant calculation using Gaussian elimination work on rings with specific properties (for the Faddeev–LeVerrier algorithm the restriction is on the characteristic of the ring, for Gaussian elimination the ring must be an integral domain (ideally a field)). * Ring-learning with errors (for post-quantum cryptography and homomorphic cryptography). Here, a specific ring is the central object. * Number-Theoretic Transform (NTT): Basically a generalization of the Fourier Transform to the ring Z_n. Important for arbitrary-precision integer arithmetic * Chinese Remainder Theorem. Often only formulated for the ring Z, but it can be generalized to larger classes of rings. Used for example in Shamir’s scheme for secret sharing (cryptography) * The theory of BCH and Reed-Solomon codes uses a specific ring * The AKS Primality Test (a really deep result in computational number theory) uses the ring Z_n[X]/(x^r-1). --- Algebras: Very often, a ring is constructed from another ring. Examples: * the polynomial ring R[X_1, ..., X_n] * The ring of (square) matrices over a ring R So, using algebras in algorithms often means: "we want to make use use of this additional structure that our (more sophisticated) ring has)". (Associative) R-algebras formalize this concept of "ring with additional structure". To just give one algorithm for polynomials: * Buchberger algorithm for computing a Gröbner basis Other examples: * Clifford algebras for a lot of geometric problems (special case: quaternions (a 4-dimensional \mathbb{R}-algebra) for rotations in \mathbb{R}^3). * If you are willing to also consider semi-rings (in this case: tropical semi-rings): the Floyd-Warshall algorithm for finding shortest paths and the Viterbi algorithm for finding the most likely sequence of states in a Hidden-Markov Model (HMM) can very elegantly formulated using the matrix semiring over the tropical semiring.