The application of Synthetic division in Polynomial theory

by fungarwai, Feb 9, 2023, 4:40 AM

Power sum of polynomial roots

Synthetic division can be applied to find the power sums of roots of a polynomial $f(x)$
by dividing $f’(x)$ with $f(x)$

$f(x)=x^2+2x-3=0$ has two real roots $x_1=-3,~x_2=1$
$f’(x)=2x+2$

$\begin{array}{c|cccccccccccc}
~ & 2 & 2 \\
-2 & ~ & -4 & 4 & -20 & 52 & -164 & 484 & -1460 & 4372 & -13124 \\
3 & ~ & ~ & 6 & -6 & 30 & -78 & 246 & -726 & 2190 & -6558 & 19686 \\
\hline
~ & 2 & -2 & 10 & -26 & 82 & -242 & 730 & -2186 & 6562 & -19682 & 19686 \end{array}$

The coefficients of the quotient show that
$\displaystyle \sum_{k=1}^2 x_k^0=2,~\sum_{k=1}^2 x_k^1=-2,~\sum_{k=1}^2 x_k^2=10,~\sum_{k=1}^2 x_k^3=-26,\dots$

This result is caused by the formula $\dfrac{f'(x)}{f(x)}=\sum_{k=0}^\infty \dfrac{1}{x^{k+1}}\left(\sum_{j=1}^n x_j^k\right)$

Reference: The application of Synthetic division in Polynomial theory (Chinese) Section 1.1.5

Proof

Example

Python program to generate Synthetic division in LaTeX code

  1. dividend=[27,-18,0];#input by user, 27x^2-18x for example
  2. divisor=[9,-9,0,1];#input by user, 9x^3-9x^2+1 for example
  3.  
  4. def roundint(x):
  5. if x == int(x):
  6. return str(int(x))
  7. else:
  8. for k in range(1,100):
  9. T=0
  10. if x*k == int(x*k):
  11. T=1;break;
  12. if T==1:
  13. return "\dfrac{"+str(int(x*k))+"}{"+str(k)+"}"
  14. else:
  15. return str(round(x,3))
  16. qlen=11;e=0;
  17. dlen=len(divisor)-1;
  18. ddlen=len(dividend);
  19. dd="~ "
  20. for k in range(0,ddlen):
  21. dividend[k]=dividend[k]/divisor[0]
  22. dd=dd+"& "+roundint(dividend[k])+" "
  23. for k in range(0,qlen-ddlen+1):
  24. dividend.append(0)
  25. dd=dd+"\\\\\n"
  26. for k in range(1,dlen+1):
  27. divisor[k]=-divisor[k]/divisor[0]
  28. q=[]
  29. q.append(dividend[0])
  30. qq="~ & "+roundint(q[0])+" "
  31. s="$\\begin{array}{c|"
  32. s2=[]
  33. for k in range(1,dlen+1):
  34. s2.append(roundint(divisor[k])+" ")
  35. for k in range(0,dlen):
  36. for i in range(0,k+1):
  37. s2[k]=s2[k]+"& ~ "
  38. for i in range(0,qlen-dlen):
  39. t=dividend[i+1]
  40. for k in range(0,dlen):
  41. tt=q[i]*divisor[k+1]
  42. s2[k]=s2[k]+"& "+roundint(tt)+" "
  43. if i-k >= 0:
  44. t=t+q[i-k]*divisor[k+1]
  45. q.append(t)
  46. if t==0:
  47. e=e+1
  48. else:
  49. e=0
  50. if e>=dlen and i>=ddlen-1:
  51. break
  52. qq=qq+"& "+roundint(t)+" "
  53. for i in range(qlen-dlen,qlen-1):
  54. if e>=dlen and i>=ddlen-1:
  55. break
  56. t=dividend[i+1]
  57. for k in range(0,dlen):
  58. if i-k < qlen-dlen:
  59. t=t+q[i-k]*divisor[k+1]
  60. q.append(t)
  61. qq=qq+"& "+roundint(t)+" "
  62. for k in range(0,qlen+1):
  63. s=s+"c"
  64. s=s+"}\n"+dd
  65. for k in range(0,dlen):
  66. s=s+s2[k]+"\\\\\n"
  67. s=s+"\\hline\n"+qq+"\\end{array}$"
  68. print(s)


pywindow code
This post has been edited 1 time. Last edited by fungarwai, Feb 9, 2023, 4:57 AM

modular arithmetic on 1^1+2^2+3^3+...+n^n

by fungarwai, Dec 13, 2021, 1:45 PM

To find the modular residue $1^1+2^2+3^3+\dots+n^n \pmod{p^s}$,

the main idea is rewriting $1^1+2^2+3^3+\dots+n^n$ as
$1^1+2^2+\dots+(p-1)^{p-1}+p^p$
$+(p+1)^1+(p+2)^2+\dots+(2p-1)^{2p-1}+(2p)^{2p}+\dots$
$=\sum_{r=1}^{p-1}\sum_{k=1}^N (pk-p+r)^{pk-p+r}+\sum_{k=1}^N (pk)^{pk}+\sum_{k=N+1}^n k^k$

While $s$ is enough small, $\sum_{k=1}^N (pk)^{pk}\pmod{p^s}$ would be simply zero.

$\sum_{k=N+1}^n k^k$ has to be calculated manually. Make it as short as it can.

Here $\sum_{r=1}^{p-1}\sum_{k=1}^N (pk-p+r)^{pk-p+r}\pmod{p^s}$ is the main problem.

$p^{s-1}\mid N\implies \sum_{k=1}^N (pk-p+1)^{pk-p+1}
\equiv (1-\frac{p}{2})N\equiv 
\begin{cases} 0 \pmod{p^s} & p=2\\
N\pmod{p^s} & p\neq 2\end{cases}$

Proof

$\varphi(p^s)=p^{s-1}(p-1)\mid N \Rightarrow \sum_{k=1}^N (pk-p+r)^{pk-p+r}
\equiv 0 \pmod{p^s} (2\le r\le p-1)$

Proof

Example

Python program for general cases

input values for n, m to get $\sum_{k=1}^n k^k\pmod{m}$

  1. n = int(input("n="))
  2. m = int(input("m="))
  3. sum=0;
  4. for k in range(1,n+1):
  5. p=1
  6. for t in range(1,k+1):
  7. p=(p*k) % m
  8. sum=(sum+p) % m
  9. print(sum)


input values for N, p, s to get $\sum_{k=1}^N (pk-p+r)^{pk-p+r}\pmod{p^s}$ for $1\le r\le p-1$

  1. N = int(input("N="))
  2. p = int(input("p="))
  3. s = int(input("s="))
  4. sum=0;m=p**s;
  5. for r in range(1,p):
  6. for k in range(1,N+1):
  7. P=1
  8. for t in range(1,p*(k-1)+r+1):
  9. P=(P*(p*(k-1)+r)) % m
  10. sum=(sum+P) % m
  11. print(sum, "when r=",r)
This post has been edited 2 times. Last edited by fungarwai, Dec 14, 2021, 12:15 PM

The product of fraction with arithmetic sequence

by fungarwai, Sep 20, 2020, 2:38 AM

Summation with polynomial roots

by fungarwai, May 26, 2020, 12:52 PM

Reciprocal type

$\sum_{i=1}^m \frac{1}{x-x_i}=\frac{f'(x)}{f(x)},~f(x)=\prod_{i=1}^m (x-x_i)$

Credit to the idea posted by ccmmjj in mathchina forum

Proof

$\sum_{i=1}^m \frac{-1}{(x-x_i)^2}=\frac{f''(x)f(x)-[f'(x)]^2}{[f(x)]^2}$

$\sum_{i=1}^m \frac{2}{(x-x_i)^3}=\frac{f'''(x)[f(x)]^2-3f''(x)f'(x)f(x)+2[f'(x)]^3}{[f(x)]^3}$

Identity of a conditional symmetric polynomial

Let $\displaystyle S_{n,m}=\sum_{r_1+r_2+\cdots+r_m=n} x_1^{r_1}x_2^{r_2}\cdots x_m^{r_m},~\sigma_{k,m} =\sum_{1\le j_1 < j_2 < \cdots < j_k \le m} x_{j_1} \dots x_{j_k}$
$\displaystyle \boxed{S_{j,m}=\sum_{k=1}^{m-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{m-1}\sigma_{m,m} S_{j-m,m}}$
$\displaystyle \text{or}~ \boxed{S_{j,m}=\sum_{k=1}^{j-1} (-1)^{k-1} \sigma_{k,m} S_{j-k,m}+(-1)^{j-1}\sigma_{j,m}}$

Proof

Example

$\displaystyle S_{j,K}=\sum_{k=1}^{M-1} (-1)^{k-1}
\sigma_{k,M} S_{j-k,K}+(-1)^{M-1}\sigma_{M,M}S_{j-M,K},~\forall K\le M\le m$

Proof

Example

Lagrange polynomial type

$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}
=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\end{cases}$

Proof

$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}
=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\\
\displaystyle
\boxed{\sum_{r_1+r_2+\cdots+r_m=n-m+1} x_1^{r_1}x_2^{r_2}\cdots x_m^{r_m}}
 & n\ge m
\end{cases}$

$S_{m,m}=\sum a$
$S_{m+1,m}=\sum a^2+\sum ab$
$S_{m+2,m}=\sum a^3+\sum a^2 b+\sum abc$
$S_{m+3,m}=\sum a^4+\sum a^3 b+\sum a^2 b^2+\sum a^2 bc+\sum abcd$

Best Proof Credit to the idea with four variables posted by natmath at #2

Proof Credit to the idea with three variables posted by gasgous at #10

Other Proof

$S_{n,m}=\sum_{i=1}^m x_i^n \prod_{j=1\atop i\neq j}^m\frac{1}{x_i-x_j}=\begin{cases}0 & 0\le n\le m-2\\1 & n=m-1\\
\displaystyle
\boxed{\sum_{r_1 + 2r_2 + \cdots + mr_m = s \atop r_1\ge 0, \ldots, r_m\ge 0} (-1)^n \frac{(r_1 + r_2 + \cdots + r_m)!}{r_1!r_2! \cdots r_m!} \prod_{i=1}^m (-\sigma_{i,m})^{r_i}} & n=s+m-1\ge m
\end{cases}$

where $\sigma_{k,m} =\sigma_k (x_1 , \ldots , x_m )=\sum_{1\le  j_1 < j_2 < \cdots < j_k \le m} x_{j_1} \dots x_{j_k}$

$S_{m,m}=\sigma_{1,m}$
$S_{m+1,m}=\sigma_{1,m}^2-\sigma_{2,m}$
$S_{m+2,m}=\sigma_{1,m}^3-2\sigma_{1,m}\sigma_{2,m}+\sigma_{3,m}$
$S_{m+3,m}=\sigma_{1,m}^4-3\sigma_{1,m}^2\sigma_{2,m}+\sigma_{2,m}^2-2\sigma_{1,m}\sigma_{3,m}+\sigma_{4,m}$

Proof

Example
This post has been edited 23 times. Last edited by fungarwai, May 19, 2023, 12:07 PM

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

20 shouts
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5839
  • Total comments: 8
Search Blog
a