Is this polynomial a square?

Question

Given an integral polynomial \$p\$, determine if \$p\$ is a square of another integral polynomial.

An integral polynomial is a polynomial with only integers as coefficients.

For example, \$x^2+2x+1\$ should gives truthy, because \$x^2+2x+1 = (x+1)^2\$.

On the other hand, \$2x^2+4x+2\$ should gives falsy: \$2x^2+4x+2 = (\sqrt{2}x+\sqrt{2})^2\$. but \$\sqrt{2}x+\sqrt{2}\$ is not an integral polynomial.

Input

A polynomial, in any reasonable format. For example, the polynomial \$x^4-4x^3+5x^2-2x\$ may be represented as:

• a list of coefficients, in descending order: [1,-4,5,-2,0];
• a list of coefficients, in ascending order: [0,-2,5,-4,1];
• a list of pairs of (coefficient, degree), in any order: [(1,4),(-4,3),(5,2),(-2,1),(0,0)];
• a map with degrees as keys and coefficient as values: {4:1,3:-4,2:5,1:-2,0:0};
• a string representation of the polynomial, with a chosen variable, say x: "x^4-4*x^3+5*x^2-2*x";
• a built-in polynomial object, e.g., x^4-4*x^3+5*x^2-2*x in PARI/GP.

Output

A value representing whether the polynomial is a square. You can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

This is code-golf, so the shortest code in bytes wins.

Testcases

Here I use coefficient lists in descending order:

Truthy

[]
[25]
[1,2,1]
[1,2,1,0,0]
[1,4,0,-8,4]
[4,28,37,-42,9]
[4,0,-4,4,1,-2,1]
[1,-12,60,-160,240,-192,64]

Falsy

[-1]
[24,1]
[1,111]
[2,4,2]
[1,2,1,0]
[1,3,3,1]
[1,-4,5,-2,0]
[4,0,-4,4,1,2,1]
[1,-9,30,-45,30,-9,1]

Answer 1

JavaScript (Node.js), 102 bytes

a=>a.some(n=>(b[j=i]=b.map(m=>n-=m*~~b[j--])|b[0]?n/2/b[0]:n**.5)%(1/a[i+i++]?1:1/0)!=0,b=[],i=0)|1&~i

Try it online!

Input a list of coefficients, in descending order. The list should either contain only a zero or the first value in the list should be non-zero.

I believe it is correct. But I cannot prove it with my math knowledge. It at least passed all testcases.

Answer 2

Python3, 289 bytes:

R=range
def m(a,b):
 r={}
 for x,y in a:
  for j,k in b:r[y+k]=r.get(y+k,0)+x*j
 return[(r[i],i)for i in r]
def c(d,k=[]):
 if[]==d:yield k;return
 for x in R(abs(d[0][0])+1):
  for e in R(d[0][1]+1):
   for i in[1,-1]:yield from c(d[1:],k+[(i*x,e)])
f=lambda x:any(x==m(i,i)for i in c(x))

Try it online!

Basic brute force.

Answer 3

Vyxal, 33 32 bytes

h√d£0¾ȦλȮḂÞ•-¥/J;RI÷?₂J†^¥J:⌊=JA

Try it Online!

–1 per emanresu A.

How?

We find the square root of the polynomial using its power series, checking if the result has several integers followed by zeroes, plus additional checks.

           #                   stack (top ->)
h          # head              p0
 √         # square root       sqrt(p0)
  d        # double            2sqrt(p0)
   £       # set register    = 2k

0¾Ȧ        # top[0] = []       [[],p1,…,p(2n)]

λ          # λ(acc,cur)        acc cur
           #                 = [a1,…,an] p(n+1)
 Ȯ         # over              [a1,…,an] p(n+1) [a1,…,an]
  Ḃ        # dup and reverse   [a1,…,an] p(n+1) [a1,…,an] [an,…,a1]
   Þ•      # dot product       [a1,…,an] p(n+1) a1an+…+ana1
     -     # subtract          [a1,…,an] p(n+1)-a1an-…-ana1
      ¥    # push register     [a1,…,an] p(n+1)-a1an-…-ana1 2k
       /   # divide            [a1,…,an] (p(n+1)-a1an-…-ana1)/2k
           #                 = [a1,…,an] a(n+1)
        J; # join              [a1,…,an,a(n+1)]

R          # reduce            [a1,…,a(2n)]
 I         # halve             [[a1,…,an],[a(n+1),…,a(2n)]]
  ÷        # split to stack    [a1,…,an] [a(n+1),…,a(2n)]
   ?       # push input        [a1,…,an] [a(n+1),…,a(2n)] [p0,…,p(2n)]
    ₂      # length even?      [a1,…,an] [a(n+1),…,a(2n)] 0
     J     # join              [a1,…,an] [a(n+1),…,a(2n),0]
      †    # vectorized not    [a1,…,an] [1,…,1]
           # [if perfect square, then a(n+1) = … = a(2n) = 0,
           # and the length of input, 2n+1, would be odd]

^          # flip stack        [1,…,1] [a1,…,an]
 ¥         # push register     [1,…,1] [a1,…,an] 2k
  J        # join              [1,…,1] [a1,…,an,2k]
   :       # dup               [1,…,1] [a1,…,an,2k] [a1,…,an,2k]
    ⌊      # floor             [1,…,1] [a1,…,an,2k] [a1,…,an,2k]
     =     # equal?            [1,…,1] [1,…,1]
           # [if perfect square, then a0 = 2k, … , an would
           # all be integers]

J          # join              [1,…,1]
 A         # all truthy?       1

Answer 4

Python NumPy, 103 bytes

lambda a:any(poly1d(rint((a[0]**.5*poly(sort(around(roots(a),7))[::2])).real))**2-a)
from numpy import*

Attempt This Online!

Inverted output: False for squares and True for non squares.

Direct approach using roots/linear factors. Floating point issues may lurk at some point (but not with the given test cases).

Basically, we take every other root, multiply corresponding linear factors and the square root of the leading coefficient, discard imaginary and fractional components, square and compare to the input.

For those not familiar with legacy numpy polynomials: roots takes a vector coefficients and returns tthe vector of roots. poly takes a vector of roots and returns the vector of coefficients of the monic polynomial with the given roots (with multiplicity). poly1d takes a vector of coefficients and returns a polynomial object. This changes semantics of basic algebraic operations.

Python NumPy, 149 bytes

lambda l,a:all([any(poly1d(rint((fft.ifft(fft.fft(a)**.5*(1-2*int_([*bin(i)[3:]]))))[:l//2+1].real))**2-a)for i in r_[1<<l:2<<l]])
from numpy import*

Attempt This Online!

Inverted output. Takes the number of coefficients and the coefficient list.

This computes the square root directly in the Fourier domain. Unfortunately, for each Fourier coefficient we have to check both signs, making this approach more complicated than I had hoped.

Answer 5

Wolfram Language (Mathematica), 58 68 64 55 bytes

thanks @Steffan for the byte correction, and the suggestions
thanks @alephalpha

Tr[Last/@Mod[a=FactorList@#,2]]<2&&EvenQ[2√a[[1,1]]]&

This code factorizes the input polynomial and checks if the exponent of all factors is even and if the square root of the integer factor is an integer.

Try it online!

Answer 6

Ruby, 122 bytes

->b{w=b.sum &:abs;(z=*-w..w).product(*[z]*k=b.size/2).any?{|c|x=-1;b==b.map{(0..x+=1).sum{|y|(a=c[x-y])&&c[y]?c[y]*a:0}}}}

Try it online!

Sheer brute force.

Answer 7

Charcoal, 56 bytes

﹪Ｌθ²Ｆ⟦§θ⁰↨θΠ⊗⊕↔θ⟧«≔×⁰↨ι⁴ζＦＬ櫧≔ζκ¹§≔ζꬋιＸ↨²ζ²»¿⁻ιＸ↨²ζ²⎚

Try it online! Link is to verbose version of code. Does not support empty lists (use [0] instead). Outputs a Charcoal boolean, i.e. - if it thinks the polynomial is a square, nothing if not. Explanation: Since @tsh beat me to my original algorithm I've gone for this approach instead but I can only prove that it has no false negatives. If someone can come up with a counterexample I'll delete this answer pending a rewrite using @tsh's approach. Edit: A counterexample was found, but @Nitrodon's claim is that only polynomials of odd degree can be counterexamples, so I've spent 5 bytes checking that the polynomial is of even degree. Edit: Another counterexample was found, so I've spent 6 bytes checking that the leading coefficient is a perfect square.

﹪Ｌθ²

Output a - if the polynomial is of even degree.

Ｆ⟦§θ⁰↨θΠ⊗⊕↔θ⟧«

Calculate a very large integer given by taking the absolute values of all of the coefficients, incrementing and doubling them, and then taking the product. Evaluate the polynomial at this value. Loop over the leading coefficient of the polynomial and the result.

≔×⁰↨ι⁴ζＦＬ櫧≔ζκ¹§≔ζꬋιＸ↨²ζ²»

Perform a binary search for the nearest integer to the square root of this value.

¿⁻ιＸ↨²ζ²⎚

If its square does not equal the value, clear the output.

Answer 8

Jelly, 26 bytes

Ærm2ÆṛJ}¹?×AṪ½Ɗ×þ`ŒdṙLƊṚ§⁼

A monadic Link that accepts a non-empty list of coefficients ordered by degree* and yields 1 if the input represents the square of an integer polynomial, or 0 if not.

* i.e. the reverse order to the examples in the question, and \$0\$ being [0] rather than []

Try it online!

How?

Same approach as loopy walt's Python answer:

• get the polynomial with every other root of the polynomial defined by the input
• rescale using the square root of the coefficient of the highest degree in the input
• get the coefficients of the square of that polynomial
• check if that is equal to the input

Just a little fiddly when the input defines a constant since we find no roots whereupon finding coefficients would error (this is why J}¹? is there).

Ærm2ÆṛJ}¹?×AṪ½Ɗ×þ`ŒdṙLƊṚ§⁼ - Link: list of coefficients, C
Ær                         - get the roots of the polynomial P defined by C
  m2                       - modulo-2 slice
         ?                 - if...
        ¹                  - ...condition: no-op (falsey if P is just a constant)
    Æṛ                     - ...then: get polynomial coefficients
       }                   - ...else: use the right argument (implicitly C) with:
      J                    -            range of length (in this case that's [1])
                             (call this list NewCoefficients)
              Ɗ            - last three links as a monad - f(C):
           A               -   absolute values
            Ṫ              -   tail (absolute of coefficient of highest degree)
             ½             -   square root
          ×                - (NewCoefficients) multiplied by (that)
                 `         - use as both arguments of:
                þ          -   table of:
               ×           -     multiplication
                      Ɗ    - last three links as a monad - f(X=that)
                  Œd       -   anti-diagonals of X (starts with main, sweeps South-East)
                                 (has the effect of grouping product coefficients by degree)
                     L     -   length of X
                    ṙ      -   rotate (the anti-diagonals) left by (length of X)
                                 (ensures that the groups are sorted by degree descending)
                       Ṛ   - reverse
                        §  - sums (sum each group of like-degree product coefficients)
                         ⁼ - equals C?

Answer 9

PARI/GP, 8 bytes

issquare

Attempt This Online!

A boring built-in. Return 1 for truthy and 0 for falsy.

---

PARI/GP, 68 bytes

p->p&&for(i=!r=(abs(Vec(p)[1])^.5\/1)*x^d=#p\2,d,r+=(q=p-r^2)\r/2)+q

Attempt This Online!

Return 0 for truthy and 1 for falsy.

Basically a port of @tsh's JavaScript answer. Interestingly, the loop body r+=(p-r^2)\r/2 looks very similar to the formula of calculating the square root of a real number using Newton's method.

Answer 10

Mathematica, 144 bytes

Based on Factorization of polynomials.

The critical function used here is FactorList[expr, GaussianIntegers -> False]

---

Golfed version(It can be golfed much more). Try it online!

f[x_]:=Module[{a},If[IntegerQ@x,Return[!SquareFreeQ@x]];a=FactorList[x,GaussianIntegers->0];If[a[[1,1]]<2,a=a~Drop~1];AllTrue[a,EvenQ[#[[2]]]&]]

Ungolfed version. Try it online!

Clear["Global`*"];
f[expr_] := Module[{fl},
  If[IntegerQ@expr, Return[Not@SquareFreeQ[expr]]]; 
  fl = FactorList[expr, GaussianIntegers -> False];
  If[fl[[1, 1]] == 1, fl = Drop[fl, 1]];
  AllTrue[fl, EvenQ[#[[2]]] &]]
truthy = FromDigits[#, x] & /@ {{}, {25}, {1, 2, 1}, {1, 2, 1, 0, 
     0}, {1, 4, 0, -8, 4}, {4, 28, 37, -42, 9}, {4, 0, -4, 4, 1, -2, 
     1}, {1, -12, 60, -160, 240, -192, 64}};
falsy = FromDigits[#, x] & /@ {{-1}, {24, 1}, {1, 111}, {2, 4, 2}, {1,
      2, 1, 0}, {1, 3, 3, 1}, {1, -4, 5, -2, 0}, {4, 0, -4, 4, 1, 2, 
     1}, {1, -9, 30, -45, 30, -9, 1}};
Print["Truthy tests:", f /@ truthy]
Print["Falsy tests:", f /@ falsy]