nhaliday + algebra   82

Rational Sines of Rational Multiples of p
For which rational multiples of p is the sine rational? We have the three trivial cases
[0, pi/2, pi/6]
and we wish to show that these are essentially the only distinct rational sines of rational multiples of p.

The assertion about rational sines of rational multiples of p follows from two fundamental lemmas. The first is

Lemma 1: For any rational number q the value of sin(qp) is a root of a monic polynomial with integer coefficients.

[Pf uses some ideas unfamiliar to me: similarity parameter of Moebius (linear fraction) transformations, and finding a polynomial for a desired root by constructing a Moebius transformation with a finite period.]


Lemma 2: Any root of a monic polynomial f(x) with integer coefficients must either be an integer or irrational.

[Gauss's Lemma, cf Dummit-Foote.]

nibble  tidbits  org:junk  analysis  trivia  math  algebra  polynomials  fields  characterization  direction  math.CA  math.CV  ground-up 
july 2019 by nhaliday
Factorization of polynomials over finite fields - Wikipedia
In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

All factorization algorithms, including the case of multivariate polynomials over the rational numbers, reduce the problem to this case; see polynomial factorization. It is also used for various applications of finite fields, such as coding theory (cyclic redundancy codes and BCH codes), cryptography (public key cryptography by the means of elliptic curves), and computational number theory.

As the reduction of the factorization of multivariate polynomials to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article.


In the algorithms that follow, the complexities are expressed in terms of number of arithmetic operations in Fq, using classical algorithms for the arithmetic of polynomials.

[ed.: Interesting choice...]


Factoring algorithms
Many algorithms for factoring polynomials over finite fields include the following three stages:

Square-free factorization
Distinct-degree factorization
Equal-degree factorization
An important exception is Berlekamp's algorithm, which combines stages 2 and 3.

Berlekamp's algorithm
Main article: Berlekamp's algorithm
The Berlekamp's algorithm is historically important as being the first factorization algorithm, which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its time complexity is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field.

[ed.: This actually looks fairly implementable.]
wiki  reference  concept  algorithms  calculation  nibble  numerics  math  algebra  math.CA  fields  polynomials  levers  multiplicative  math.NT 
july 2019 by nhaliday
Diophantine approximation - Wikipedia
- rationals perfectly approximated by themselves, badly approximated (eps>1/bq) by other rationals
- irrationals well-approximated (eps~1/q^2) by rationals:
nibble  wiki  reference  math  math.NT  approximation  accuracy  levers  pigeonhole-markov  multi  tidbits  discrete  rounding  estimate  tightness  algebra 
august 2017 by nhaliday
Structure theorem for finitely generated modules over a principal ideal domain - Wikipedia
- finitely generative modules over PID isomorphic to sum of quotients by decreasing sequences of proper ideals
- never really understood the proof of this in Ma5b
math  algebra  characterization  levers  math.AC  wiki  reference  nibble  proofs  additive  arrows 
february 2017 by nhaliday
nt.number theory - Is $x^{2k+1} - 7x^2 + 1$ irreducible? - MathOverflow
Here is a proof, based on a trick that can be used to prove that x^n+x+1 is irreducible when n≠2 mod 3.
q-n-a  overflow  math  algebra  tidbits  math.NT  contradiction  polynomials  nibble  multiplicative 
january 2017 by nhaliday
infinitely divisible matrices
the use of Hilbert spaces for establishing matrices are Gram matrices (and hence PSD) is interesting
tidbits  math  algebra  pdf  yoga  linear-algebra  inner-product  positivity  signum 
august 2016 by nhaliday
Opetopic - Home
Opetopic is an experimental graphical proof assistant for higher category theory.
math  algebra  worrydream  visualization  tools  ide  math.CT 
july 2016 by nhaliday
« earlier      
per page:    204080120160

bundles : academeframemath

related tags

abstraction  accretion  accuracy  acm  additive  advanced  advice  alg-combo  algebra  algebraic-complexity  algorithms  analysis  aphorism  applications  approximation  arrows  atoms  bare-hands  bayesian  berkeley  better-explained  big-list  big-picture  binomial  books  boolean-analysis  bounded-cognition  business  calculation  cartoons  characterization  checking  chemistry  clarity  classic  clever-rats  coding-theory  cog-psych  commutativity  complexity  composition-decomposition  computation  concept  conceptual-vocab  concrete  confluence  contradiction  core-rats  counterexample  course  creative  criminal-justice  cs  curiosity  darwinian  data-science  database  debugging  decision-making  decision-theory  definition  degrees-of-freedom  devtools  differential  dimensionality  direction  discrete  discussion  draft  duality  dynamical  economics  efficiency  electromag  elegance  encyclopedic  engineering  entropy-like  error  estimate  ethics  examples  existence  exocortex  expert  expert-experience  explanation  exposition  extratricky  extrema  fields  form-design  formal-methods  formal-values  fourier  game-theory  games  geometry  giants  gotchas  gowers  graph-theory  graphs  grokkability  grokkability-clarity  ground-up  growth  GT-101  guessing  heavyweights  heuristic  hi-order-bits  high-variance  history  hmm  homepage  howto  hsu  ide  identification-equivalence  identity  IEEE  iidness  impro  info-dynamics  info-foraging  information-theory  init  inner-product  insight  integral  interdisciplinary  intricacy  intuition  israel  iteration-recursion  janus  knowledge  language  latex  learning  lecture-notes  lectures  lens  lesswrong  let-me-see  letters  levers  libraries  lifts-projections  linear-algebra  links  list  logic  lol  lower-bounds  machine-learning  macro  madhu-sudan  magnitude  markov  matching  math  math.AC  math.AG  math.AT  math.CA  math.CO  math.CT  math.CV  math.DS  math.FA  math.GN  math.GR  math.MG  math.NT  math.RT  mathtariat  measure  meta:math  meta:research  metabuch  metameta  methodology  metrics  michael-nielsen  micro  minimalism  mit  mixing  moments  monotonicity  mostly-modern  motivation  multi  multiplicative  music-theory  necessity-sufficiency  neuro  nibble  nitty-gritty  numerics  old-anglo  oly  oly-programming  org:bleg  org:edu  org:junk  overflow  oxbridge  p:**  p:someday  p:whenever  papers  parsimony  pcp  pdf  people  philosophy  physics  pic  pigeonhole-markov  poetry  polynomials  positivity  pragmatic  pre-2013  prioritizing  probabilistic-method  probability  problem-solving  prof  programming  proofs  properties  pseudorandomness  psychology  puzzles  python  q-n-a  qra  quantum  quixotic  quotes  rationality  ratty  reading  rec-math  recommendations  reference  reflection  relativity  research  review  rigidity  rigor  roadmap  rounding  s:*  s:**  s:***  scholar  scitariat  signum  simplification-normalization  skunkworks  smoothness  social-science  soft-question  span-cover  spectral  stackex  stanford  stat-mech  stats  stories  stream  structure  subculture  survey  synthesis  tcs  tcstariat  teaching  technical-writing  techtariat  tensors  thermo  thick-thin  thinking  thurston  tidbits  tightness  tip-of-tongue  tools  top-n  topics  topology  tracker  tricki  trivia  troll  uniqueness  unit  vague  video  visual-understanding  visualization  volo-avolo  von-neumann  water  wiki  wisdom  wordlessness  world-war  wormholes  worrydream  writing  yak-shaving  yoga  zooming  👳  🤖  🦉 

Copy this bookmark: