Constructing Faithful Homomorphisms over Fields of Finite Characteristic
Prerona Chatterjee Ramprasad Saptharishi

	
	Phase diagram of the spin-1/2 Heisenberg alternating chain in a magnetic field
    Yin-Zhong Wu
    December 30, 2023
==============================================================================



	
		We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena <cit.>, and exploited by them, and Agrawal, Saha, Saptharishi and Saxena <cit.> to design algebraic independence based identity tests using the Jacobian criterion over characteristic zero fields. An analogue of such constructions over finite characteristic fields was unknown due to the failure of the Jacobian criterion over finite characteristic fields. 
		
		Building on a recent criterion of Pandey, Saxena and Sinhababu <cit.>, we construct explicit faithful maps for some natural classes of polynomials in the positive characteristic field setting, when a certain parameter called the inseparable degree of the underlying polynomials is bounded (this parameter is always 1 in fields of characteristic zero). This presents the first generalisation of some of the results of Beecken  <cit.> and Agrawal  <cit.> in the positive characteristic setting.		
	
        


§ INTRODUCTION

	
Multivariate polynomials are fundamental objects in mathematics. 
These are the primary objects of study in algebraic complexity with regard to classifying their hardness as well as algorithmic tasks involving them. 
The standard computational model for computing multivariate polynomials is algebraic circuits. 
These are directed acyclic graphs with internal nodes labelled by `+' and `×' gates having the obvious operational semantics, and  leaves are labelled by the input variables or field constants. 
	
An important concept about relationships between polynomials is the notion of algebraic dependence. 
A set of polynomials = f_1,…, f_m⊂[] is said to be algebraically dependent if and only if there is some nonzero polynomial combination of f_1,…, f_m that is zero. 
Such a nonzero polynomial A(z_1,…, z_m) ∈[], if one exist, for which A(f_1,…, f_m) = 0 is called the annihilating polynomial for the set f_1, …, f_m. 
For instance, if f_1 = x, f_2 = y and f_3 = x^2+y^2, then A = z^2_1 + z^2_2 - z_3 is an annihilator. Note that the underlying field is very important. 
For example, the polynomials x+y and x^p + y^p are algebraically dependent over _p, but algebraically independent over a characteristic zero field.
	
Algebraic independence is very well-studied and it is known that algebraically independent subsets of a given set of polynomials form a matroid (see <cit.>). 
Hence, the size of the maximum algebraically independent subset of  is well-defined and is called the algebraic rank or transcendence degree of . 
We denote it by () = (f_1, …, f_m).
	
Several computational questions arise from the above definition. 
For instance, given a set of polynomials = f_1, …, f_m, each f_i given in its dense representation, can we compute the algebraic rank of this set efficiently?
What if the f_i's are provided as algebraic circuits?
Such a nonzero polynomial A(z_1,…, z_m) ∈[], if one exist, for which A(f_1,…, f_m) = 0 is called the annihilating polynomial for the set f_1, …, f_m. 
Furthermore, in instances when () = m-1, Kayal <cit.> showed that the smallest degree annihilating polynomial is unique. 
There could be various questions about the minimal degree annihilator in this case. For instance, can we compute it efficiently? 
Kayal <cit.> showed that even checking if the constant term of the annihilator is zero is -hard, and evaluating the annihilator at a given point is #-hard. 
In fact, recently Guo, Saxena, Sinhababu <cit.> showed that even in the general case, checking if the constant term of every annihilator is zero is -hard. 
This effectively rules out any attempt to compute the algebraic rank via directly checking properties of the annihilating polynomials.
	
Despite this, over fields of characteristic zero, algebraic rank has an alternate characterisation via the Jacobian criterion. 
Jacobi <cit.> showed that the algebraic rank of a set of polynomials (⊆[]) is given by the linear rank (over the rational function field ()) of the Jacobian of these polynomials. 
This immediately yields a randomized polynomial time algorithm to compute the algebraic rank of a given set of polynomials by computing the rank of the Jacobian evaluated at a random point due to the polynomial identity lemma <cit.>.
	


  §.§.§ Faithful homomorphisms and PIT

Algebraic independence shares a lot of similarities with linear independence due to the matroid structure. 
One natural task is to find a rank-preserving transformation in this setting. This is defined by what are called faithful homomorphisms.
	
 
	Let = f_1,…, f_m⊆[] be a set of polynomials. If 𝕂 is an extension field of , a homomorphism 
	Φ: [] →𝕂[] 
	is said to be an -faithful homomorphism for f_1,…, f_m if
	
    _f_1,…, f_m = _Φ(f_1),…, Φ(f_m).


	
Ideally, we would like a faithful homomorphism with ≈ and 𝕂 =. 
Beecken, Mittmann and Saxena <cit.> showed that a generic -linear homomorphism to () many variables would be an -faithful homomorphism with high probability. 
	
One important consequence of faithful homomorphisms is that they preserve nonzeroness of any polynomial composition of f_1, …, f_m.
	

	Suppose f_1, …, f_m ∈[x_1, …, x_n] and Φ is an -faithful homomorphism for f_1, …, f_m. 
	Then, for any circuit C(z_1, …, z_m) ∈[z_1,…, z_m], we have 
    C(f_1, …, f_m) = 0 ⇔ C(Φ(f_1),…, Φ(f_m)) = 0.



Thus, constructing explicit faithful homomorphisms can also be used for polynomial identity testing (PIT), which is the task of checking if a given algebraic circuit C computes the identically zero polynomial. 
For PIT, the goal is to design a deterministic algorithm that runs in time polynomial in the size of the circuit. 
There are two types of PIT algorithms, whitebox and blackbox — in the blackbox setting, we are only provided evaluation access to the circuit and some of its parameters (such as degree, number of variables, size etc.). 
Thus blackbox PIT algorithms for a class  is equivalent to constructing a hitting set, which is a small list of points in S ⊂^n such that any nonzero polynomial f∈ is guaranteed to evaluate to a nonzero value on some ∈ S.
	
It follows from <ref> that if we can construct explicit -faithful homomorphisms for a set f_1,…, f_m whose algebraic rank is k ≪ n, then we have a variable reduction that preserves the nonzeroness of any composition C(f_1,…, f_m). 
This approach was used by Beecken, Mittmann and Saxena <cit.> and Agrawal, Saha, Saptharishi, Saxena <cit.>, in the characteristic zero setting, to design identity tests for several subclasses by constructing faithful maps for f_1,…, f_m with algebraic rank at most k = O(1), when

	
  * each f_i is a sparse polynomial,
	
  * each f_i is a product of multilinear, variable disjoint, sparse polynomials,
	
  * each f_i is a product of linear polynomials,

and further generalisations.
	
All the above constructions crucially depend on the fact that the rank of the Jacobian captures algebraic independence. 
However, this fact is true only over fields of characteristic zero and hence all the above results no longer hold over fields of positive characteristic. 
	


  §.§.§ Algebraic independence over finite characteristic

	
A standard example to exhibit the failure of the Jacobian criterion over fields of finite characteristic, is x^p-1y, y^p-1x — these polynomials are algebraically independent over _p but the Jacobian is not full-rank over _p. 
Pandey, Saxena and Sinhababu <cit.> characterised the extent of failure of he Jacobian criterion for f_1,…, f_m by a notion called the inseparable degree associated with this set (formally defined in <ref>). 
Over characteristic zero fields, this is always 1 but over fields of characteristic p this is a power of p. 
In their work, Pandey  presented a Jacobian-like criterion to capture algebraic independence.
Informally, each row of the generalized Jacobian matrix is obtained by taking the Taylor expansion of f_i( + ) about a generic point, and truncating to just the terms of degree up to the inseparable degree[Over characteristic zero, the inseparable degree is 1 and this is just the vector of first order partial derivatives]. 
The exact characterisation is more involved and is presented in <ref> but we just state their theorem here. 
	
theoremPSS<cit.>
	Let f_1, …, f_k be a set of n-variate polynomials over a field  with inseparable degree t. Also, for a generic point , let _t(f_i) = _≤ t(f_i( + ) - f_i()). 
	Then, they are algebraically dependent if and only if 
	
    ∃ (α_1, …, α_k) (≠0) ∈()^k  s.t. ∑_i=1^k α_i ·_t(f_i) = 0 _t(f_1), …, _t(f_k)^≥ 2_() + ^t+1.



We note that although the statement above seems slightly different from the one in <cit.>, it is not too hard to see that they are actually equivalent. 
In their paper, Pandey  have stated their criterion in terms of functional dependence. 
However, stated this way, it clearly generalises the traditional Jacobian criterion. 
	
In the setting when the inseparable degree is constant, this characterisation yields a randomized polynomial time algorithm to compute the algebraic rank. 
Thus, a natural question is whether this criterion can be used to construct faithful homomorphisms for similar classes of polynomials as studied by Beecken  <cit.> and Agrawal  <cit.>. 
	

	Recently, Guo  <cit.> showed that the task of testing algebraic independence is in ∩ via a very different approach. 
	However, it is unclear if their algorithm also yields constructions of faithful homomorphisms or applications to PIT in restricted settings. 

	
Following up on the criterion of Pandey, Saxena and Sinhababu <cit.> for algebraic independence over finite characteristic, we extend the results of Beecken  <cit.> and Agrawal  <cit.> to construct faithful homomorphisms for some restricted settings. 
	
theoremFaithfulMaps
	Let f_1,…, f_m ∈[x_1,…, x_n] be such that f_1,…, f_m = k and the inseparable degree is t. 
	If t and k are bounded by a constant, then we can construct a polynomial (in the input length) sized list of homomorphisms of the form Φ:[] →(s)[y_0, y_1,…, y_k] such that at least one of them is guaranteed to be -faithful for the set f_1,…, f_m, in the following two settings:
	
		
  * When each of the f_i's are sparse polynomials,
		
  * When each of the f_i's are products of variable disjoint, multilinear, sparse polynomials.
	

	
Prior to this, construction of faithful homomorphisms over finite fields was known only in the setting when each f_i has small individual degree <cit.>. 
Over characteristic zero fields, the inseparable degree is always 1 and hence the faithful maps constructed in <cit.>, <cit.> over such fields can be viewed as special cases of our constructions. 
	
The above theorem also holds for a few other models studied by Agrawal  <cit.> (for instance, occur-k products of sparse polynomials).
We mention the above two models just as an illustration of lifting the recipe for faithful maps from <cit.> to the finite characteristic setting. 
As corollaries, we get efficient PIT algorithms for these models.
	
corollaryCorSparsePIT
	If f_1, …, f_m∈[x_1, …, x_n] is a set of s'-sparse polynomials with algebraic rank k and inseparable degree t where k,t = O(1). 
	Then, for the class of polynomials of the form C(f_1,…, f_m) for any polynomial C(z_1,…, z_m) ∈[], there is an explicit hitting set of size s'·(C)^O(1).

	
corollaryCorMLPIT	
	Let = ∑_i=1^m T_i be a depth-4 multilinear circuit of size s, where each T_i is a product of variable-disjoint, s-sparse polynomials. 
	Suppose T_1,…, T_m∈[x_1, …, x_n] is a set of polynomials with algebraic rank k and inseparable degree t where k,t = O(1). 
	Then, for the class of polynomials of the form C(T_1,…, T_m) for any polynomial C(z_1,…, z_m) ∈[], there is an explicit hitting set of size s·(C)^O(1).

	


  §.§.§ Comparison with the PIT of <cit.>

	
Pandey <cit.> also give a PIT result in their work for circuits of the form ∑_i  f_i,1⋯ f_i,m where f_i,1, …, f_i,m≤ k for every i and each f_i,j is a degree d polynomial in [x_1, …, x_n].
They extend the result of Kumar and Saraf <cit.> to arbitrary fields by giving quasi-polynomial time hitting sets if kd is at most poly-logarithmically large.
	
<ref> however is incomparable to the PIT of Pandey  <cit.> for the following reasons:

	
  * The algebraic rank bound in the case of <cit.> is a gate-wise bound rather than a global bound. 
	Thus, in principle, it could be the case that f_i,1,…, f_i,m is bounded by k for each i but this would not necessarily translate to a bound on ∏_j f_i,ji as demanded in <ref>. 
	Hence, in this regard, the PIT of <cit.> is stronger.
	
  * In the regime when we have ∏_j f_i,ji and the inseparable degree of this set to be bounded by a constant, <ref> presents an explicit hitting set of polynomial size, whereas it is unclear if <cit.> provide any non-trivial upper bound as this does not translate to any bound on f_i,1,…, f_i,m. 

	


  §.§.§ On other models studied by Agrawal  <cit.>

	
Our results, in its current form, do not extend directly some of the other models studied by Agrawal  <cit.>, most notably larger depth multilinear formulas. 
The primary hurdle appears to be the recursive use of explicit faithful homomorphisms for larger depth formulas. 
In the characteristic p setting, unfortunately, it is unclear if a bound on the inseparable degree of the original gates can be used to obtain a bound on the inseparable degree of other sets of polynomials considered in the recursive construction of Agrawal  <cit.>. 
	


 §.§ Proof overview

	
The general structure of the proof follows the outline of Agrawal  <cit.>'s construction of faithful homomorphisms in the characteristic zero setting. Roughly speaking, this can be described in the following steps:
	

	
  Step 1: For a generic linear map Φ: →(s)[y_1,…, y_k], write the Jacobian of the set of polynomials f_1 ∘Φ, ⋯, f_k∘Φ. 
	Thus can be described succinctly as a matrix product of the form
	
    J_(f ∘Φ) = Φ(J_()) ·  J_(Φ()).

	
  Step 2: We know that J_() is full rank. 
	Ensure that Φ(J_()) (where Φ is applied to every entry of the matrix J_()) remains full rank. 
	This can be done if 's are some structured polynomials such as sparse polynomials, or variable-disjoint products of sparse polynomials etc.
	
  Step 3: Choose the map Φ so as to ensure that
	
    (Φ(J_()) ·  J_(Φ())) = (Φ(J_())).

	This is typically achieved by choosing Φ so as to make J_(Φ()) a rank-extractor. 
	It was shown by Gabizon and Raz <cit.> that a parametrized Vandermonde matrix has this property and this allows us to work with a homomorphism of the form (loosely speaking)
	
    Φ: x_i ↦∑_j=1^k s^ij y_j.


	
We would like to execute essentially the same sketch over fields of finite characteristic but we encounter some immediate difficulties. 
The criterion of Pandey  <cit.> over finite characteristic is more involved but it is reasonably straightforward to execute Steps 1 and 2 in the above sketch using the chain rule of (Hasse) derivatives. 
The primary issue is in executing Step 3 and this is for two very different reasons.
	
The first is that, unlike in the characteristic zero setting, the analogue of the matrix J_(Φ()) has many correlated entries. 
In the characteristic zero setting, we have complete freedom to choose Φ so that J_(Φ()) can be any matrix that we want. 
Roughly speaking, we only have n · k parameters to define Φ but the analogue of J_(Φ()) is much larger in the finite characteristic setting. 
Fortunately, there is just about enough structure in the matrix that we can show that it continues to have some rank-preserving  properties. 
This is done in <ref>.
	
The second hurdle comes from the subspace that we need to work with in the modified criterion. 
The rank-extractor is essentially parametrized by the variable s. In order to show that it preserves the rank of Φ(J_()) under right multiplication, we would like to ensure that the variable s effectively does not appear in this matrix. 
In the characteristic zero setting, this is done by a suitable restriction on the other variables to remove any dependencies on s in Φ(J_()). 
Unfortunately, in the criterion of Pandey  <cit.>, we have to work modulo some suitable subspace and these elements introduce other dependencies on s that appear to be hard to remove. 
Due to this hurdle, we are unable to construct (s)-faithful homomorphisms even in restricted settings. 
	
However, we observe that for the PIT applications, we are merely required to ensure that f_1 ∘Φ, …, f_k∘Φ remain -algebraically independent instead of (s)-algebraically independent. 
With this weaker requirement, we can obtain a little more structure in the subspace involved and that lets us effectively execute Step 3. 
	


  §.§.§ Structure of the paper

	
We begin with a description of some preliminaries that are necessary to understand the criterion of Pandey, Saxena and Sinhababu <cit.> in the next section. 
Following that, in <ref>, we show that certain Vandermonde-like matrices have rank-preserving properties. 
We use these matrices to give a recipe of constructing faithful maps, in <ref>, and execute this for the settings of <ref> in <ref>. 
	
	


§ PRELIMINARIES




 §.§ Notations

	

	
  * For a positive integer m, we will use [m] to denote set 1,2,…, m. 
	
  * We will use bold face letters such as  to denote a set of indexed variables x_1,…, x_n. 
	In most cases the size of this set would be clear from context.
	Extending this notation, we will use ^ to denote the monomial x_1^e_1⋯ x_n^e_n. 
	
  * For a set of polynomials f_1,…, f_m, we will denote by f_1,…, f_m_𝕂 the set of all 𝕂-linear combinations of f_1,…, f_m. 
	Extending this notation, we will use f_1,…, f_m_𝕂^r to denote the set of all 𝕂-linear combinations of r-products f_i_1⋯ f_i_r (with i_1,…, i_r∈ [m]) and f_1,…, f_m_𝕂^≥ r similarly. 
	In instances when we just use f_1,…, f_m, we will denote the ideal generated by f_1,…, f_m. 

	


 §.§ Hitting set generators


Hitting set generators are defined as follows.
	

	Let  be a class of n-variate polynomials. 
	A tuple of polynomials 𝒢 = (G_1(α),…, G_n(α)) is a hitting set generator for  if for every nonzero polynomial P() ∈ we have P(G_1(α),…, G_n(α)) is a nonzero polynomial in α.
		
	The degree of this generator is defined to be max(G_i). 

	
Intuitively, such a tuple can be used to generate a hitting set for  by running over several instantiations of α. 
Also, it is well known that any hitting set can be transformed into an HSG via interpolation. 
	


 §.§ Isolating weight assignments

Suppose : x_i→ is a weight assignment for the variables x_1, …, x_n.
We can extend it to define the weight of a monomial as follows.

    (^) = ∑_i=1^n e_i ·(x_i)



	A weight assignment : x_i→ is said to be isolating for a set S of monomials if every pair of distinct monomials in S receives distinct weights.

	
Note that if the highest degree of a monomial in S is d, then assigning the weight (x_i) = (d+1)^i is trivially isolating for S. 
However, in this case the weight of a monomial can become exponentially large in n. 
	
In the case when S = (n), results by Klivans and Spielman <cit.> or Agrawal and Biswas <cit.> show that if we define (x_i) = (d+1)^i  p, then it suffices to go over (n) many `p's to guarantee that one of these weight assignments isolates the monomials in S. 
The weight of a monomial in this case is thus bounded by (n).
	


 §.§ Some field theoretic preliminaries
	
We present some basic preliminaries about field extensions. 
	

	A polynomial is said to be separable if it does not have repeated roots in a field where it factorises completely.

	
Over characteristic zero fields, ever irreducible univariate polynomial is separable since it cannot have a common root with its derivative. 
However, this is not the case over fields of finite characteristic as derivatives of non-trivial polynomials could become zero. 
This adds some subtlety in field extensions over finite characteristic.
	
We mention some basic facts about field extensions; these may be found in any standard text for field theory <cit.>. 

	
  * An extension 𝕂/ is said to be algebraic if every element in 𝕂 is the root of some polynomial over . Otherwise, it is transcendental. 
	
  * For a transcendental extension 𝕂/, a transcendence basis is a maximal subset of 𝕂 that is algebraically independent over . 
	An extension 𝕂/ is purely transcendental if there is a transcendence base S ⊆ such that 𝕂 = (S).
	
  * An algebraic extension 𝕂/ is said to be separable if the minimal polynomial of every element in 𝕂 is separable.
		
	An example of an algebraic extension that is not separable is _p(x) / _p(x^p). 
	The minimal polynomial μ(z) for x over _p(x^p) is z^p - x^p, which is not separable. 
		
	Further, if 𝕂 = (α_1, …, α_n) is an algebraic extension of , then 𝕂/ is separable if and only if the minimal polynomials of α_i over  is separable for each i. 

	
For an algebraic extension 𝕂/ over characteristic p the separable closure of  in 𝕂, denoted by (𝕂/), is defined as

    (𝕂/) = α∈𝕂the minimal polynomial of α is separable over .


For every element α in 𝕂∖(𝕂/), we would have that α^p^i∈(𝕂/) for some positive integer i. 
Thus, the extension 𝕂/ splits into two extensions 𝕂≥(𝕂/) ≥ where the latter is a separable algebraic extension and the former is a purely inseparable algebraic extension. 
	

	For an algebraic extension 𝕂/ of characteristic p, the inseparable degree of the extension, denoted by (𝕂/), is the smallest t such that x^t∈(𝕂/) for every x∈𝕂. 

	

	The above definition deviates slightly from the standard definition texts on field theory, where the inseparable degree is defined to be the degree of the extension 𝕂/(𝕂/F). 
	The definition above is the one used by Pandey, Saxena and Sinhababu <cit.> in their criterion and we stick with it in this paper. 

	
We would like to extend this definition to non-algebraic extensions. 
Let f_1,…, f_m be a set of polynomials over . 
We will be interested in the extension () = (x_1,…, x_n) over (f_1,…, f_m). 
Suppose f_1,…, f_k is a separable transcendence basis of f_1,…, f_m. 
Using the matroid property of algebraically independent polynomials, there exists x_i_k+1,…, x_i_n such that f_1,…,f_k, x_i_k+1,…, x_i_n is algebraically independent as well. 
Now, since () is algebraic over (f_1,…, f_k,x_i_k+1,…, x_i_n), we can talk about the inseparable degree of this algebraic extension. 
We use this to define a suitable notation of inseparable degree[This definition is non-standard, but is sufficient for the purposes of this paper and the criterion of Pandey, Saxena and Sinhababu <cit.>] for a set of algebraically independent polynomials.  
	

	Let = f_1,…, f_m be a set of polynomials over a field  of characteristic p. 
	For a set S ⊆ [n], define _S = x_ii ∈ S. We shall define (f_1,…, f_k) to be
	
    min()/(, _S)[                  |S| = n - () and; (,_S)/() is purely transcendental ]


	
Intuitively, every extension can be thought of as purely transcendental, followed by a separable algebraic, followed by a purely inseparable algebraic extension. 
The above definition used the inseparable degree of the purely inseparable part of this in the general case. 
	
With this background, we are now ready to state the criterion for algebraic independence over fields of finite characteristic. 
Similar to the Jacobian Criterion, Pandey, Saxena and Sinhababu <cit.> reduce the problem of checking algebraic independence to that of checking linear independence. 
However, their criterion is slightly more subtle in the sense that we will have to check the linear independence of a set of vectors modulo a large subspace.
	


 §.§ The PSS Criterion over fields of finite characteristic

	
A set of polynomials f_1, …, f_m∈[x_1, …, x_n] is said to be algebraically dependent if there exists a polynomial 0 ≠ A ∈[z_1, …, z_m] such that A(f_1, …, f_m) = 0. 
If such a polynomial A() exists, we call it the annihilating polynomial for f_1, …, f_m.
	
However given a set of polynomials = f_1, …, f_m∈[], finding the annihilating polynomial if one exists is hard <cit.>. 
Nevertheless if the underlying field  has characteristic zero, the Jacobian Criterion <cit.> reduces the question of checking whether a given set of polynomials is algebraically dependent to the question of checking whether a corresponding set of vectors is linearly dependent.
	


  §.§.§ The Jacobian Criterion

For f_1, …, f_m ∈[x_1, …, x_n], the Jacobian matrix is defined as 

    _() = 
    	[ ∂_x_1(f_1) ∂_x_1(f_2)          … ∂_x_1(f_m); ∂_x_2(f_1) ∂_x_2(f_2)          … ∂_x_2(f_m);          ⋮          ⋮          ⋱          ⋮; ∂_x_n(f_1) ∂_x_n(f_2)          … ∂_x_n(f_m) ]

With this definition, the Jacobian criterion <cit.> is as follows.
	
[Jacobian criterion]
	If  is a field of characteristic zero, then f_1, …, f_m ∈[] are algebraically independent if and only if _() has full rank over the rational function field ().

	
As mentioned earlier,  this criterion is not true over fields that have finite characteristic. 
For f_1 = x^p-1y and f_2 = xy^p-1, if the underlying field is _p, then ((f_1, f_2)) = 0 even though they are algebraically independent. 
The key insight of Pandey  <cit.> is to observe that the rows of the Jacobian matrix, which are first order partial derivatives, are the linear terms present in the Taylor expansion of f() around a generic point . 
Generalising this, they study higher order terms of the Taylor expansion around a generic point to come up with a modified criterion that works over all fields. 
	


  §.§.§ Taylor Expansion and Hasse Derivatives

	
Define the following operator _t(f) := _≤ t(f( + ) - f()), where _≤ t restricts to just those monomials in  of degree at most t. 
It is also worth noting that _t(f) does not have a constant term and this would become useful in the criterion.
	
The operator _t(f) can be thought of as a vector over the field () whose coordinates are indexed by monomials ^ of degree at most t. 
The entry in the coordinate ^ of _t() is the corresponding Hasse derivative of f evaluated at :

    !/e_1!e_2!⋯ e_n!·∂^f/∂ x_1^e_1⋯∂ x_n^e_n().

	
The operator _t however, as defined above, is indexed by t. 
Pandey  <cit.> show that the correct value of t to work with is the inseparable degree of the given set of polynomials.	
Formally, we have the following statement.
	
*
	
We note that at least one direction of this theorem can be slightly generalised to give the following lemma. 
A proof is given here for the sake of completeness, but we note that the steps are almost identical to those in <cit.>.
	
lemmaPSSDep
	Let  be an algebraically closed field and 𝕂 be an extension field of . 
	Further, suppose g_1,…, g_k is a set of n-variate polynomials in 𝕂[] that are -algebraically dependent. 
	Also, for a generic point , let _t(g_i) = _≤ t(g_i( + ) - g_i()). 
	Then for any positive integer t, there exists (α_1, …, α_k) ∈(())^k ∖0 such that
	
    ∑_i=1^k α_i _t(g_i) ≡ 0 _t(g_1), …, _t(g_k)^≥ 2_(()) + ^t+1




	Suppose g_1, …, g_k are -algebraically dependent. 
	Then by standard properties of transcendence bases <cit.>, we have that there is an -algebraically independent subset of g_1, …, g_k, of size r < k, that forms a separable transcendence basis.
	Without loss of generality, let that subset be g_1, …, g_r.
		
	Let A ∈[u_0, u_1, …, u_r] be the minimal annihilating polynomial for = g_0, g_1, …, g_r where g_0:=g_r+1.
	Now since A() = 0, for formal variables , we have A(( + )) = 0.
	Also, from the definition of _t(g), we have that g_j( + ) = g_j() + _t(g_j) ^t+1 for any j = 0,…, r. Hence,
	
    A(g_0() + _t(g_0),…, g_r() + _t(g_r)) = 0 ^t+1.

	
	Using Taylor expansion, we get
	
    A(g_0() + _t(g_0),…, g_r() + _t(g_r))     = ∑_≥ 0∂_^ A_ = ()· (_t())^
        =  A(()) + ∑_i=0^r ∂_u_iA_ = ()_t(g_i) 
             _t(g_0), …, _t(g_r)^≥ 2_(()) + ^t+1

	where the last equality crucially used the fact that the coefficients of A are from  and hence the linear combinations of _t()^≥ 2 are over (()). 
		
	Observe that A(()) = 0. Furthermore, since g_1, …, g_r forms a separable basis, we have that ∂_u_0 A is a nonzero polynomial. Hence ∂_u_0(A(())) ≠ 0, as A is the minimal degree annihilator for . Therefore, we have a nonzero vector (α_1,…,α_k) ∈(())^k such that
	
    ∑_i=1^k α_i _t(g_i) ≡ 0 _t(g_1), …, _t(g_k)^≥ 2_(()) + ^t+1


	


  §.§.§ A different perspective on the criterion

	
Let 𝒰_t() = 𝒰_t(f_1, …, f_k) denote the subspace _t()^≥ 2_()
 = _t(f_1), …, _t(f_k)^≥ 2_()^t+1. 
Then, for any h ∈𝒰_t(), we define the modified Jacobian matrix as follows.

    _t(, h) = [ _t(f_1) + h;     _t(f_2);           ⋮;     _t(f_k) ].

The columns of this matrix are indexed by monomials in  and entries in the column indexed by ^ are the coefficient of ^ in the corresponding rows.
	
An alternative statement for the PSS criterion is thus, the following.
 
	Let f_1, …, f_k be a set of n-variate polynomials over a field  with inseparable degree t. 
	Then, they are algebraically independent if and only if for every h ∈𝒰_t(), _t(, h) is full rank.
	
	
We note that <ref> can also be viewed from a similar perspective. 
Let 𝒱_t(g_1, …, g_k) denote the subspace _t(g_1), …, _t(g_k)^≥ 2_(())^t+1. 
An alternate statement for the lemma is then the following.
	

	Let  be any field and 𝕂 be an extension field of . 
	If g_1,…, g_k is a set of n-variate polynomials in 𝕂[] that are -algebraically dependent, then for any positive integer t, there exists h' ∈𝒱_t(g_1, …, g_k) such that _t(, h') is not full rank.

	


§ RANK CONDENSERS FROM ISOLATING WEIGHT ASSIGNMENTS

	
In this section, we focus on rank-preserving properties of certain types of matrices. 
These are slight generalisations of similar properties of Vandermonde matrices that were proved by Gabizon and Raz <cit.> that would be necessary for the application to constructing faithful homomorphisms. 
	

	Suppose we have a matrix of the form:
	
    V = [  s^w_1 s^2w_1      … s^nw_1;  s^w_2 s^2w_2      … s^nw_2;                    ⋮;  s^w_n s^2w_n      … s^nw_n ]

	where w_i < w_j whenever i < j. 
	If V' is a matrix obtained from V by replacing some of the non-diagonal entries by zero, then (V') ≠ 0 and furthermore ((V')) = ∑_i=1^n i · w_i.



	Since 
	
    (V') = ∑_σ∈ S_n(σ) ∏_i ∈ [n] V'[i, σ(i)],

	the monomial corresponding to σ being the identity permutation contributes a nonzero monomial of degree ∑ i· w_i. 
	We will show that all other terms of (V') will have smaller degree. 
		
	Suppose σ is not the identity permutation, we must have i ≠σ(i) for some index i; let i_0 be the first such index. 
	Define j such that σ(j) = i_0 and π = σ∘ (i_0  j). 
	Note that π(i_0) = σ(j) = i_0 and fixes the first i_0 indices. 
	Furthermore, π(i)= σ(i) for all i ≠ i_0,j. Thus,
	
    ∑_i=1^n (π(i) - σ(i)) · w_i    = (π(i_0) - σ(i_0)) · w_i_0 + (π(j) - σ(j)) · w_j 
       = (σ(j) - σ(i_0)) · w_i_0 + (σ(i_0) - σ(j)) · w_j 
       = (σ(i_0) - σ(j)) · (w_j - w_i_0) > 0

	Repeating this exercise until we reach the identity permutation, we have that the monomial contributed by the diagonal has the largest degree. 

	

	Let A be a matrix over a field  with k rows and columns indexed by monomials in  of degree at most D that is full-rank. 
	Further, let w = (w_1, …, w_n) be an isolating weight assignment for the set of degree D monomials, and let (^) = ∑_i=1^n w_i e_i.
		
	Suppose M_Φ is a matrix whose rows are indexed by monomials in  of degree at most D, and columns indexed by pure monomials y_i^di∈1,…, k , d≤ D given by
	
    M_Φ(^, y_i^d) = 
    		s^i ·(^)   if (^) = d
    
    		0    otherwise.

	where s is a formal variable. 
	Then, _(s)(A · M_Φ) = _(A).

	

	By the Cauchy-Binet formula, if we restrict M_Φ to a set T of k-columns, then
	
    ( A · M_Φ[T]) = ∑_S ⊆Columns(A)
    |S| = k(A[S]) ·(M_Φ[S,T])

	We wish to show that the above sum is nonzero for some choice of columns T. 
	We do that by first defining a weight function on minors of A, then proving that there is a unique nonzero minor of A of largest weight, and then choosing a set of columns T such that the degree of (M_Φ[S,T]) coincides with this chosen weight function.
	Define the weight of a minor of A as follows: 
		
	
		Suppose the columns of the minor is indexed by S = ^𝐞_1, …, ^𝐞_𝐤 with the property that (^𝐞_1) < (^𝐞_2) < ⋯ < (^𝐞_𝐤). 
		Define the weight of this minor as
		
    (S) = ∑_i=1^k i ·(^𝐞_𝐢)

		where, recall, (^𝐞_𝐢) = ∑_j w_j ·𝐞_𝐢(j). 
	  
		
	 
		There is a unique nonzero k× k minor of A of maximum weight. 
	
	
	
		Suppose S_1 and S_2 are two different minors of A with the same weight. 
		We will just identify S_1 and S_2 by the set of column indices for simplicity. 
		Say S_1 has columns indexed by ^𝐞_1, …, ^𝐞_𝐤 with (^𝐞_1) < (^𝐞_2) < ⋯ < (^𝐞_𝐤) and S_2 has columns indexed by ^𝐞'_1, …, ^𝐞'_𝐤 with (^𝐞'_1) < (^𝐞'_2) < ⋯ < (^𝐞'_𝐤).
			
		Suppose S_1 and S_2 agree on the first i columns, that is _j = _j' for all j ≤ i, and say (_i+1) < (_i+1'). 
		By the matroid property, there must be some column ^_j' from S_2 that we can add to S_1 ∖^_i+1 so that S = S_1 ∖^_i+1^_j' is also a nonzero minor of A. 
		Suppose that
		
    (^_1) < ⋯ < (^_i+r) < (^_j') < (^_i+r+1) < ⋯ < (^_k).

		Then,
		
    (S)     =  ∑_a=1^i a ·(^_a) + ∑_a=i+2^i+r (a-1) ·(^_a) + (i+r) (^_j') + ∑_a=i+r+1^k a ·(^_a)
        > ∑_a=1^i a ·(^_a) + (i+1) (^_j') + ∑_a=i+2^k a ·(^_a)
         > ∑_a=1^k a ·(^_a) = (S_1)

			
		Hence, there cannot be two different nonzero minors of A of the same weight. 
		Thus, the nonzero minor of largest weight is unique. 
	
		
	We will now choose k columns from M_Φ, as follows, in such a way that the degree of the corresponding determinant agrees with the weight function. 
	Note that the matrix M_Φ has a natural block-diagonal structure based on the degree of the monomials indexing the rows and columns. 
	
		
  * Let S_0 be the unique k × k minor of A having maximum weight. 
		Further, assume its columns are indexed by ^𝐞_1, …, ^𝐞_𝐤 with (^𝐞_1) < (^𝐞_2) < … < (^𝐞_𝐤).
		Let d_i = (^_i) = ∑_j (_i)_j. 
		
  * Choose the columns T = y_1^d_1, y_2^d_2,…, y_k^d_k of the matrix M_Φ. 
	
	By <ref>, for any set of S'⊆Columns(A), we have ((M_Φ[S',T])) ≤(S') and furthermore we also have (M_Φ[S_0,T]) = (S_0) as we chose the columns T to ensure that the main diagonal of the sub-matrix has only nonzero elements. 
	Hence,
	
    ( A · M_Φ[T]) = ∑_S ⊆Columns(A)
    |S| = k(A[S]) ·(M_Φ[S,T]) ≠ 0

	since the contribution from (A[S_0]) (M_Φ[S_0,T]) is the unique term of highest degree and so cannot be cancelled.  

	


§ CONSTRUCTION OF EXPLICIT FAITHFUL MAPS

	
We will be interested in applying a map Φ:[] →(s)[] and study the transformation of the PSS-Jacobian. 
Since the entries of the PSS-Jacobian involve _t(f()) = _≤ tf( + ) - f(), we would need to also work with _t(g()) where g() = f ∘Φ. 
To make it easier to follow, we shall use a different name for the variables in the two cases. Hence,

    _t(f()) := _≤ tf( + ) - f()  ,  _t(g()) := _≤ tg( + ) - g().

	


 §.§ Recipe for constructing faithful maps

	
Let f_1, …, f_m ∈[x_1, …, x_n] be polynomials with f_1, …, f_m = k and inseparable degree t. 
We will work with linear transformations of the form: 

    Φ:x_i    ↦ a_i y_0 + ∑_j=1^k s^w_i · j y_j,  for all i∈ [n],
    Φ_z:z_i    ↦ a_i v_0 + ∑_j=1^k s^w_i · j v_j,  for all i∈ [n].

where all the variables on the RHS are formal variables. 
Further, define g_1, …, g_m∈[] as g_i = f_i ∘Φ and _t(g_i) = _≤ t(g_i( + ) - g_i()).
	
The main lemma of this section is the following recipe for constructing faithful maps. 
	
 
	Let f_1, …, f_m ∈[] be polynomials such that their algebraic rank is at most k and suppose the inseparable degree is bounded by a constant t. 
	Further,
	
		
  * suppose 𝒢 = (G_1(α),…, G_n(α)) = (a_1, …, a_n) is such that for some ∈𝒢, the rank of _t(, h) is preserved after the substitution →.
		
  * suppose w:[n]→ is an isolating weight assignment for the set of n-variate monomials of degree at most t. 
	
		
	Then, the homomorphism Φ: [x_1,…, x_n] →(s,α)[y_0,…, y_k] defined as 
	
    Φ: x_i ↦ y_0 G_i(α) + ∑_j=1^k y_j·  s^w(i) j,

	is an -faithful homomorphism for the set f_1, …, f_m. 

	
As mentioned earlier, the rough proof sketch would be to first write the PSS-Jacobian of the transformed polynomials  in terms of , express that as a suitable matrix product, and use some rank extractor properties of the associated matrix, as described in <ref>. 
The rest of this section will execute this sketch. 
	
 
	Let Φ:→(s)[] and Φ_z:→(s)[] be given as above. 
	Further, for any polynomial h'(a_1,…, a_m) ∈(())[], define h(a_1,…, a_m) ∈(())[] as follows.
	
		_^(h) is got by replacing every occurrence of g_i() by f_i() in _^(h')
	  
	Then, 
	
    h'(_t(g_1), …, _t(g_m)) = Φ∘Φ_z(h(_t(f_1), …, _t(f_m))).


	
It is worth noting that the polynomial h(a_1,…, a_m) is independent of s, by definition. 
This would be crucial later on in the proof. 
	

	Firstly, note that h is well defined. 
	This is because by the definition of g_1, …, g_m, if _^(h') ∈(()) has a nonzero denominator then by replacing the g_i()s with f_i() in it, it will continue to remain nonzero.
		
	The claim now follows essentially from the fact that Φ is linear and homogeneous in .
	
    _t(f ∘Φ)(, )    = _≤ t(f ∘Φ)( + ) - (f∘Φ)()
        = _≤ tf(Φ() + Φ_z()) - f(Φ_z())   (by linearity in )
        = Φ∘Φ_z(_t(f))    (by homogeneity in )

	and it extends to higher degree terms just from the fact that Φ and Φ_z are homomorphisms and that Φ does not change the degree (in  and ).
	Further, note that if h(a_1,…, a_m) = ∑_ h_·^ then 
	
    h' = ∑_Φ_z(h_) ·^.

	Thus, 
	
    h'(_t(g_1), …, _t(g_m))    = ∑_Φ_z(h_) · (_t(∘Φ))^
       = ∑_Φ_z(h_) ·Φ∘Φ_z(_t()^)
        = ∑_ (Φ∘Φ_z(h_)) ·Φ∘Φ_z(_t()^)     (h_ is independent of )
       = Φ∘Φ_z ∑_ h_·_t()^    (Φ and Φ_z are homomorphisms)
       = Φ∘Φ_z(h(_t(f_1), …, _t(f_m)))


	
 
	Suppose A' is a matrix whose columns are indexed by monomials in . 
	Further suppose a row in A' corresponds to a polynomial, say h'(_t()) = h'(_t(g_1), …, _t(g_m)) ∈(())[], whose entry in the column indexed by ^ is _^(h'(_t())) ∈(, ). 
	If A is the corresponding matrix (having entries from ()) with columns indexed by monomials in  and the corresponding row being h(_t(f_1), …, _t(f_m)) ∈(())[] as described in <ref>, then
	
    A' = Φ_z(A) ×M_Φ

	where M_Φ(^, ^) = _^(Φ(^)).

	
 
	Suppose h(_t(f_1), …, _t(f_m)) = ∑_ h_() ·^. 
	Then,
	
    h'(_t(g_1), …, _t(g_m))     = Φ∘Φ_z(h(_t(f_1), …, _t(f_m)))    (by <ref>)
        = ∑_ h_(Φ_z()) ·Φ(^) 
        = ∑_ h_(Φ_z())·∑__^(Φ(^)) ·^
        = ∑_∑_ h_(Φ_z()) ·_^(Φ(^))·^

	
	Thus, the coefficient of ^ in h'(_t(g_1), …, _t(g_m)) is
	
    ∑_Φ_z(h_()) ·_^(Φ(^))

	which gives the required matrix decomposition.

	
We are now in a position to prove <ref>. 
	

	Without loss of generality, say f_1,…, f_k is an algebraically independent set. 
	We wish to show that if g_i = f_i ∘Φ, then g_1, …, g_k is an -algebraically independent set as well. 
	Assume on the contrary that g_1, …, g_k is an -algebraically dependent set. 
	Then for t being the inseparable degree of f_1, …, f_k, by <ref>, there exists
	
    h' ∈𝒱_t(g_1, …, g_k) := _t(g_1), …, _t(g_k)^≥ 2_(())^t+1

	such that _t(, h') is not full rank. 
	Without loss of generality, we can assume that the entries of _t(, h') are denominator-free by clearing out any denominators. 
	Corresponding to h', define h as in <ref>, which would also satisfy that
	
    h ∈𝒰_t(f_1, …, f_k) := _t(f_1), …, _t(f_k)^≥ 2_()^t+1.

	It is worth stressing the fact that the polynomial h is independent of the variable s. 
	Then by <ref> we get
	
    _t(, h') = Φ_z(_t(, h)) ×M_Φ.

	Now, if we substitute v_0 = 1 and v_i =0 for every i ∈ [k], we get
	
    _t(, h')(v_0 = 1, v_1 = … = v_k = 0) = _t(, h) ( = 𝐆(α)) ×M_Φ.

	But since f_1, …, f_k is algebraically independent, <ref> yields that _t(, h) has full rank. 
	Thus, for the correct choice of α, _t(, h) ( = 𝐆(α)) also has full rank by the property we assumed 𝒢 has. 
	Most crucially, the matrix _t(,h) is independent of the variable s.
		
	To complete the proof, we need to show that multiplication by M_Φ continues to keep this full rank to contradict the initial assumption that _t(,h') was not full rank. 
		
	Finally note that for the Φ we have defined, M_Φ restricted to only the pure monomial columns
	
    y_i^ji ∈1,…, k , j ∈0,1,…, t,

	is the same as M_Φ as defined in <ref>. 
	Further, w is an isolating weight assignment for the set of n-variate monomials of degree at most t, we satisfy the requirements of  <ref>. 
	Hence, by <ref>,
	
    _(s,α)_t(,h')(v_0 = 1, v_1 = …, v_k = 0)    = _(α)_t(, h)( = 𝐆(α))
    _(s,α,)_t(,h')   ≥_(α)_t(, h)( = 𝐆(α))
        = k,

	which contradicts our assumption that it was not full rank. 
	Hence, it must indeed be the case that f_1 ∘Φ,…, f_k ∘Φ is  - algebraically independent.
 
	


§ EXPLICIT FAITHFUL MAPS AND PIT APPLICATIONS IN RESTRICTED SETTINGS

	
We now describe some specific instantiations of the recipe given by <ref> in restricted settings. 
Let us first recall the statement of the main theorem. 
	
*
	

	By <ref>, Φ: [x_1,…, x_n] →(s,α)[y_0,…, y_k] defined as 
	
    Φ: x_i ↦ y_0 G_i(α) + ∑_j=1^k y_j·  s^w(i) j,

	is a faithful homomorphism for the set f_1, …, f_m if w = (w_1, …, w_n) is an isolating weight assignment for n-variate monomials of degree at most t, and for any h ∈𝒰_t(), 𝒢 = (G_1(α),…, G_n(α)) is such that the rank of _t(, h) is preserved after the substitution → for some ∈𝒢. 
	We define the weight using the standard hashing techniques <cit.>.
		
	

  
*Defining w Define w : [n] → as 
	
    w(i) = (t+1)^i p

	where t is the inseparable degree. 
	
	Assuming t to be a constant, there are only (n) many distinct monomials in  of degree at most t. 
	Thus, standard results by Klivans and Spielman <cit.> or Agrawal and Biswas <cit.> shows that it suffices to go over (n) many `p's before w isolates all monomials in  of degree at most t. 

	Let _t() be the matrix with columns indexed by monomials in  of degree at most t and rows by k-variate monomials ^ in degree at most t, defined as follows.
	
    _t()[^, ^] = _^(_t()^)

	Set K = k+t  t to be the number of rows in _t(). 
	Then the following is true.
		
	
		If 𝒢 is a hitting set generator for every K' × K' minor of _t() where K' ≤ K, then the rank of _t(, h) is preserved for every h ∈𝒰_t().
	
	
	
		We need to show that there is an  in 𝒢 which has the following property:
			
		
			For any h ∈𝒰_t(), if _t(f_1) + h, _t(f_2), …, _t(f_k) are linearly independent, then so are _t(f_1)() + h(), _t(f_2)(), …, _t(f_k)().
		 
			
		Now suppose this is not the case. 
		Then it must be the case that without loss of generality, some h ∈𝒰_t(), _t(, h) has full rank but for any ∈𝒢,  
		
    α_1 (_t(f_1)() + h()) + ∑_i=2^k (α_i ·_t(f_i)()) = 0.

		Here, not all of α_i_i ∈ [k] are zero. 
		However by our hypothesis, this would mean that
		
    α_1 (_t(f_1) + h) + ∑_i=2^k (α_i ·_t(f_i)) ≠ 0.

			
		Let ℬ be a basis of the rows in _t(, h). 
		Then each of _t(f_1) + h, _t(f_2), …, _t(f_k) can be written in terms of rows in ℬ. 
		Thus, the above statement can be rewritten as
		
    ∑_i=1^K'β_i · b_i = α_1 (_t(f_1)+h) + ∑_i=2^k (α_i ·_t(f_i)) ≠ 0

		where β_i_i ∈ [K'] are some scalars, b_i ∈ℬ and K' = ℬ.
			
		This shows that not all β_i_i=1^K' can be zero. 
		Now since 𝒢 is a hitting set generator for every K' × K' minor in _t(), there is some ∈𝒢 such that b_i()_i ∈ [K'] continue to remain linearly independent. 
		Thus, ∑_i=1^K'β_i × b_i()≠ 0, since not all β_i_i ∈ [K'] is zero. 
		However, this shows that
		
    α_1 (_t(f_1)()+h()) + ∑_i=2^k (α_i ·_t(f_i)()) = ∑_i=1^K'β_i × b_i() ≠ 0.

			
		This contradicts our assumption, and so it must be the case that for any h ∈𝒰_t(), the rank of _t(, h) is preserved.
	
		
	Now it is only a question of finding a hitting set generator of low degree, for every K' × K' minor of _t() where K' ≤ K.
		
	

 §.§ Defining 𝒢 when f_i's are sparse
 
	When the f_i's are s-sparse, every entry of () is a sum of products of at most t Hasse-derivatives of the f_i's. 
	Further the number of such products is at most n+tt, and hence each entry of () has sparsity at most n+tt· s^t. 
	When k,t are constants, then any K × K minor of () has sparsity s^O(1) and hence standard hitting-set generators for sparse polynomials <cit.> would be sufficient in this setting.
		
	

 §.§ Defining 𝒢 when f_is are products of variable disjoint, multilinear, sparse polynomials

	In exactly along the same lines as Agrawal  <cit.>, we can construct hitting-set generators for minors of () when each f_i is a product of variable disjoint, multilinear, sparse polynomials.
		
	The key observation is that when k,t = O(1), any K× K minor of () only involves derivatives over constantly many variables, say x_1,…, x_ℓ with ℓ≤ Kt. Since each f_i is a product of variable disjoint sparse polynomials, each row of this submatrix can be expressed as a common factor F and a product of ℓ sparse polynomials. 
	The reason is as follows.
	
		If f = g . g' where g' is independent of variables in S ⊆x_1, …, x_n, then for any monomial ^ that depends only on S we have 
		
    _^(_t(f)) = _^(_t(g)) . g'(z).

	 
	Hence, the determinant of this matrix is a product of sparse polynomials (each of sparsity at most s^Kt = (s) when k,t = O(1)). 
	Once again, standard hitting-set generators for sparse polynomials <cit.> are sufficient in this case as well.

	


 §.§ Applications to PIT

	
Using <ref>, two straightforward corollaries for PIT for related models. 
	
*
	

	Without loss of generality, we may assume that  is algebraically closed (since nonzeroness of polynomials remain unchanged when interpreted as polynomials over an extension). 
	Suppose f_1,…, f_k is a separable transcendence basis for f_1,…, f_m with inseparable degree t.
		
	By <ref>, we have a polynomial sized list of maps Φ_i: [] →[s,y_0,…, y_k,α], each of degree (n) such that at least one of them is -faithful for f_1,…, f_k (and hence also for f_1,…, f_m); let Φ be such a -faithful homomorphism. From the construction of <ref>, the homomorphism Φ has degree (s').  
	By <ref>, we know that C(f_1,…, f_m) = 0 if and only if Φ(C(f_1,…, f_m)) is zero. Now that Φ(C(f_1,…, f_m)) is a polynomial in k+3 = O(1) variables, we can use the hitting set obtained from the polynomial identity lemma <cit.> to give hitting set of size (s',(C)) for C(f_1,…, f_m). 

	
Along exactly the same lines, we get the following corollary in the case when we are working with depth-4 multilinear circuits of small algebraic rank and inseparable degree. 
	
*
	
As mentioned in the introduction, the above result is incomparable with the PIT results of Pandey  <cit.> and Kumar and Saraf <cit.>. 
	


§ CONCLUSION AND OPEN PROBLEMS

	
We studied the task of constructing faithful homomorphisms in the finite characteristic setting and extended the results of Agrawal  <cit.> in the setting when the inseparable degree is bounded. There are some very natural open problems in this context.
	

	
  * Are the homomorphisms constructed in the paper also (s)-faithful homomorphisms?
		
	Our proof only provides a recipe towards constructing -faithful homomorphisms due to technical obstacles involving the criterion for algebraic independence over finite characteristic fields. 
	The exact point where it fails is in the proof of <ref>. 
	It is crucial that h ∈𝒰_t() is s-free for our proof to work. This is not an issue in characteristic zero fields and Agrawal  <cit.> construct (s)-faithful homomorphisms.
		
	
  * How crucial is the notion of inseparable degree in the context of testing algebraic independence?
		
	The criterion of Pandey, Saxena and Sinhababu <cit.> crucially depends on this field theoretic notion and there seems to be compelling algebraic reasons to believe that this is necessary. 
	However, as mentioned earlier, Guo, Saxena and Sinhababu <cit.> showed that algebraic independence testing is in ∩ and this proof has absolutely no dependence on the inseparable degree.




§ ACKNOWLEDGEMENTS

We acknowledge support of the Department of Atomic Energy, Government  of India, under project number RTI4001.
	
customurlbst/alphaurlpp

	
