18
\$\begingroup\$

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 , 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]
\$\endgroup\$
11
  • 1
    \$\begingroup\$ Related. Related. \$\endgroup\$
    – alephalpha
    Apr 24 at 23:49
  • 6
    \$\begingroup\$ Currently "Evaluate the polynomial as \$x = 10\$, check if result is square" passes all test cases, I'd suggest adding in a counter example, such as \$x + 111\$ \$\endgroup\$ Apr 25 at 5:05
  • 1
    \$\begingroup\$ Is it reasonable to require at least one coefficient, using [0] instead of []? \$\endgroup\$
    – Neil
    Apr 25 at 7:37
  • 4
    \$\begingroup\$ There is a safe "sufficiently large value" for non-square polynomials of even degree, and polynomials of odd degree can't be squares. \$\endgroup\$
    – Nitrodon
    Apr 25 at 17:57
  • 2
    \$\begingroup\$ @Nitrodon This might be fixed by requiring the leading coefficient to be a square. In that case, for a input polynomial \$p\$ with degree \$2d\$, we may write \$p=q^2+r\$ for some polynomials \$q\$ and \$r\$ such that \$\deg(q)=d\$, \$\deg(r)<d\$ (by repeatedly completing the square). Multiplying a sufficiently large square number, we may assume that \$q\$ and \$r\$ are integral. When \$x\$ is sufficiently large, we would have \$(q-1)^2<q^2+r<(q+1)^2\$, so \$q^2+r\$ being a square will force that \$r=0\$. \$\endgroup\$
    – alephalpha
    Apr 26 at 6:25

9 Answers 9

6
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Looks very similar to the algorithm I was planning to implement. \$\endgroup\$
    – Neil
    Apr 25 at 7:36
5
\$\begingroup\$

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.

\$\endgroup\$
1
4
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ ⟨⟩ can be ¾ \$\endgroup\$
    – emanresu A
    Jun 22 at 9:28
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
5
  • 2
    \$\begingroup\$ this is 68 bytes, not 58. also (a=FactorList@#;And@@EvenQ/@a[[2;;,2]]&&IntegerQ@[Sqrt]a[[1,1]])& a[[2;;,2]]~AllTrue~EvenQ can be And@@EvenQ/@a[[2;;,2]] for -2. and \[Sqrt] is for another -4. for another -2, replace the first a with (a=FactorList@#), and then remove the outer parens, declaration, and semicolon. \$\endgroup\$
    – Steffan
    Jun 23 at 2:09
  • \$\begingroup\$ also, I don't really undestand this, but would FactorSquareFreeList help? \$\endgroup\$
    – Steffan
    Jun 23 at 2:17
  • \$\begingroup\$ looks like it would be 50 bytes with FactorSquareFreeList without the requirement that it is a square of an integer polynomial: And@@(EvenQ@#2&@@@FactorSquareFreeList[#][[2;;]])& \$\endgroup\$
    – Steffan
    Jun 23 at 2:37
  • \$\begingroup\$ @Steffan Yeah, I was trying to use FactorSquareFreeList but didn't feel like I understood it enough to use it well. Am I correct when I say that your suggestions lead to the code And@@EvenQ/@(a=FactorList@#)〚2;;,2〛&&IntegerQ@√a〚1,1〛&? \$\endgroup\$
    – JSorngard
    Jun 23 at 10:20
  • 1
    \$\begingroup\$ Tr[Last/@Mod[a=FactorList@#,2]]<2&&EvenQ[2√a[[1,1]]]&. \$\endgroup\$
    – alephalpha
    Jun 24 at 11:48
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 56 bytes

﹪Lθ²F⟦§θ⁰↨θΠ⊗⊕↔θ⟧«≔×⁰↨ι⁴ζFL櫧≔ζκ¹§≔ζꬋιX↨²ζ²»¿⁻ιX↨²ζ²⎚

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.

﹪Lθ²

Output a - if the polynomial is of even degree.

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

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.

≔×⁰↨ι⁴ζFL櫧≔ζκ¹§≔ζꬋιX↨²ζ²»

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

¿⁻ιX↨²ζ²⎚

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ @alephalpha Now using Nitrodon's claim that my approach only fails for polynomials of odd degree. \$\endgroup\$
    – Neil
    Apr 26 at 0:18
  • \$\begingroup\$ @alephalpha If I add checks that the first and last coefficients are also perfect squares will that satisfy you? \$\endgroup\$
    – Neil
    Apr 26 at 8:50
  • \$\begingroup\$ Checking the first coefficient would be enough. I'm not sure if that large integer is sufficiently large, but I can't find any counterexample. \$\endgroup\$
    – alephalpha
    Apr 26 at 8:59
2
\$\begingroup\$

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?
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.