text:
\section{Introduction}
Over the past decade, magnetic fields have been studied for stars in a wide range of spectral classes, with a specific focus on solar-like stars of various masses, rotation rates, and ages. It has conclusively been shown that the field strength decays with age for solar-type stars \citep{VGJ14}, obeying a similar power-law to what has been obtained for the rotational period \citep{S72}. This dependence between the magnetic properties and evolutionary state implies that the dynamo mechanisms that are at play in the convective zone also evolve and adjust throughout the star's life.

Thanks to its ability to reconstruct large-scale surface magnetic fields, Zeeman-Doppler Imaging technique \citep[hereafter ZDI,][]{DB97} brought new insights to the subject establishing the critical role of the stellar internal structure on the overall topology of the large-scale field \citep{GDM12}. Typically, fully-convective stars were found to harbor strong poloidal magnetic fields with a high degree of axisymmetry, while partly-convective stars displayed weaker surface fields with a predominantly non-axisymmetric poloidal component and a significant (sometimes dominant) toroidal component \citep[e.g., ][]{DMP08, MDP08, MDP10,FPB16,FBP18}. This scenario gives hints on how dynamo processes may be acting for a range of stellar parameters - with mostly single stars studied so far.

AB~Dor is the first star on which differential rotation was detected, and it has been the subject of a large number of dedicated observing campaigns due to its key role in addressing the dynamo action in stars \citep[e.g.,][]{DCP03,JDC07}. The K2 dwarf of the V471~Tau binary system is a twin version of the single-star AB~Dor. As a member of a close binary system, involving a white dwarf of mass similar to the K2 dwarf \citep{VWV15}, tidal forces are expected to directly impact the angular momentum evolution, aiming to synchronize the rotational period with the orbital period of the system \citep{Z89}. It has been argued that tidal effects would weaken the differential rotation of the active star \citep{S81,S82}; however, the strong shear detected in the pre-main-sequence binary system HD~155555 opposes this claim \citep{DHC08}. It is still unknown whether the young age of the HD~155555 system (18~Myr) could explain the observed shear. Nevertheless, observations suggest the existence of a preferential longitude for the spots manifestation in short-period binaries, likely due to the influence of the tides on the dynamo action \citep[see][for a discussion on the formation of preferential longitudes]{HS02,HS03,HS03B}.

Being also an eclipsing binary, V471 Tau allows studying the potential impact of dynamo action and activity cycles on the observed eclipse timing variations (ETV). Although the ETVs of compact binaries are commonly associated with a third body, e.g., for NN Ser \citep{MPB14,BDH13} and QS Vir \citep{PMC10,BMP16}, in V471~Tau some authors questioned the presence of the brown dwarf necessary to explain the ETVs \citep{HSP15,VCD17}. As first proposed by \citet{A92}, stars exhibiting magnetic cycles might be capable of changing the internal mass distribution (or equivalently the quadrupole moment of the star) by redistributing angular momentum in the convective envelope. This effect is of particular interest for close binary systems, where the resulting gravity change of a companion propagates to the system, culminating in orbital period modulations. However, improvements in Applegate models challenged its feasibility to drive ETV \citep{L05,L06,VSB18}. Specifically, the inclusion of more realistic angular velocities (with radial and latitudinal dependencies) limited the Applegate effect to systems with large shear fluctuations, thus making it unlikely for most binary systems.

An alternative mechanism requiring low levels of fluctuation in the differential rotation was recently suggested to operate in V471~Tau \citep{L20}. The mechanism relies on the existence of a stationary non-axisymmetric quadrupole moment in the K2 dwarf that either librates or circulates in the orbital plane. Contrary to the Applegate effect, \citeauthor{L20}'s model requires a stationary non-axisymmetric magnetic field to sustain the quadrupole moment and drive ETV (a result of a torque introduced by magnetic structures misaligned with the line joining both companions). For V471~Tau, \citet{L20} showed that both libration and circulation scenarios could be operating in the system.

In the present work, we investigate the magnetism of the cool companion of the close-binary system V471~Tau by analyzing spectropolarimetric observations collected with ESPaDOnS in Nov/Dec 2004 and Dec 2005. This study offers a unique opportunity to examine how tides affect the magnetic topology and differential rotation compared to the single-star analog AB~Dor (similar mass, temperature, and rotational period). The evolutionary status of the system is discussed in Sec.~\ref{sec:paramsv471tau} and our data set is presented in Sec.~\ref{sec:obsdata}. After describing the ZDI technique in Sec.~\ref{sec:modelling}, we present the reconstructed maps of brightness inhomogeneities and large-scale magnetic field in Sec.~\ref{sec:maps}. Section~\ref{sec:diff} is dedicated to the positive detection of differential rotation at the surface of the star, and Sec.~\ref{sec:halpha} to the periodic behavior observed in the H$\alpha$ emission line for both epochs of observation. Finally, we discuss our results in Sec.~\ref{sec:disc}.

\section{Evolutionary Stage of V471 Tau} \label{sec:paramsv471tau}

V471~Tau is an eclipsing binary system and member of the 625~Myr old Hyades open cluster \citep{PBL98}  with a \textit{Gaia} distance of $47.51 \pm 0.03$~pc \citep{G20,BRF21}. Over the last $50$~years, V471~Tau has been extensively observed to understand the evolution of binary systems with the eclipses giving a unique opportunity to measure the orbital period of the system and its temporal variation with extreme accuracy. The current scenario indicates that the system is a pre-cataclysmic variable that has undergone a common-envelope phase in the early stages of evolution. The system consists of a hot white dwarf star (WD) and a K2 dwarf main-sequence star not yet overfilling its Roche lobe \citep{NY70}. Self-consistent analysis handling simultaneously radial velocity curves, light curves, and eclipse timings of the system yielded a WD mass of $0.8778 \pm 0.0011$~M$_{\sun}$ and a K2 dwarf mass of $0.9971 \pm 0.0012$~M$_{\sun}$, orbiting with a short-period of $P_\mathrm{orb} = 0.5211833875$~days and a separation distance of $a = 3.586~R_\star$, where $R_\star$ is the radius of the K2 dwarf \citep{VWV15}. Moreover, because of the proximity of the two companions, tides compel the K2 dwarf star to rotate synchronously with the orbital period of the system, implying that $P_\mathrm{rot} \simeq P_\mathrm{orb}$. We summarise the quantities relevant for the scope of this paper in Table~\ref{tab:paramsv471}.

\begin{table}
\addtolength{\tabcolsep}{-2pt}
    \centering
    \caption{Parameters of the K2 dwarf component of the V471~Tau system. From top to bottom: age, distance from the Earth $d$, separation distance to the companion $a$, mass $M_\star$, radius $R_\star$, effective temperature ${T_\mathrm{eff}}$, logarithm of the surface gravity $\log g$, rotational period $P_\mathrm{rot}$, inclination $i$, and line-of-sight projected equatorial rotation velocity $v\sin(i)$. }
    \label{tab:paramsv471}
    \begin{tabular}{lll}
        \hline
         Parameter              &  Value$^{ \dagger}$  & Reference    \\
         \hline
          Age~(Myr)            & 625 (50)       & \citet{PBL98}. \\
          $d$~(pc)             & 47.51 (03)     & \citet{BRF21} \\
          $a~({R_{\star}})$    & 3.586 (11)     &  \citet{VWV15}  \\
          $M_\star~({M_{\sun}})$ &  0.9971 (12) &  \citet{VWV15}    \\
         $R_\star~({R_{\sun}}) $ & 0.93709 (93) &  \citet{VWV15} \\
         ${T_\mathrm{eff}}$~(K) & 5,066 (04)     &    \citet{VWV15} \\
         $\log g$~(cm/s) &  4.49331 (87)        &  \citet{VWV15}\\
         $P_\mathrm{rot} = P_\mathrm{orb}$~(d) & 0.5211833875 (27)   &  \citet{VWV15}  \\
         $i~(\degr)$  &  78.755 (30)           & \citet{VWV15}  \\
         $v\sin(i)$~(km/s) & 89.30 (11)         & \citet{VWV15}  \\
        \hline
        \multicolumn{3}{l}{\footnotesize$^\dagger$    Standard error of the last two digits is shown inside the parenthesis.} \\
    \end{tabular}
\end{table}

Photometric studies reveal an apparent magnitude ranging from $V=9.30$ to $9.42$ for the K2 dwarf star \citep[cf. Fig.~6 in][]{VWV15}. Given the distance modulus of $-3.384\pm0.002$ and the V-band bolometric correction at the effective temperature of the K2 dwarf star, $BC_\mathrm{V}=-0.29\pm0.02$ \citep{PM13}, we estimate minimum and maximum bolometric magnitudes of $M_\mathrm{bol, min} =5.626 \pm 0.063$ and $M_\mathrm{bol, max} =5.746 \pm 0.063$, respectively. Additionally, using the radius and effective temperature listed in Table~\ref{tab:paramsv471}, as well the reference bolometric magnitude for the Sun, $M_\mathrm{bol, \sun}=4.74$, we infer the bolometric magnitude for the unspotted star, $M_\mathrm{bol, u} = 5.451 \pm 0.004$. The fraction of spots at the surface of the K2 dwarf star is then given by $f_\mathrm{spot} = 1 - 10^{\frac{2}{5}(M_\mathrm{bol, u}-M_\mathrm{bol})} \approx~0.15$--$0.25$ which falls within the observed range of magnitudes. This spottedness of 15--25~per cent is typical for active stars. Previous brightness reconstructions of the K2 dwarf star with Doppler imaging retrieved spot coverage of $\approx 0.20$ in 1992/1993 \citep{RHJ95} and 0.09 in 2002 \citep{HAS06}.

Figure~\ref{fig:evolK2} shows the K2 dwarf V471~Tau's position in the Hertzsprung-Russell diagram. Among the two evolutionary models considered, the 0.9~$M_\odot$ track of \citet{SDF00} is the one that best reproduces the stellar parameters of the K2 star. Still, we can notice the anomalous mass for its K2V spectral type that has been subject of investigations in the past years \citep[e.g.,][]{OBS01}. Some authors suggested that a metal enrichment during the common-envelope phase could potentially explain the over-mass; however, no conclusive answer exists yet \citep[see discussion in][]{VWV15}. Using the evolutionary model of  \citet{SDF00}, we infer that the radiative core of the K2 star reaches a radius of $0.68~R_\star$ at $625$~Myr (or, in other words, that it posses a convective envelope corresponding to the outer $32\%$ of the stellar radius).
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{figs/evolutionary_K2.pdf}
    \caption{Positions of the K2 dwarf V471~Tau (red square) and the single-star analog AB~Dor\protect\footnotemark\
    (green square) in the Hertzsprung-Russell diagram. \citet{SDF00} evolutionary tracks for masses $0.8 - 1.0~M_\odot$ are shown in dashed black lines ($Z=0.0020$ + overshooting model), except the $0.9~M_\odot$ track shown in continuous black line, which we chose to represent the K2 dwarf star. Siess isochrones for $10$, $30$, and $625$~Myr are represented as dotted blue lines. Evolutionary tracks from \citet{BHA15} models (dashed magenta) are included for comparison.}
    \label{fig:evolK2}
\end{figure}
\footnotetext{For the single-star analog AB~Dor, we adopt a luminosity based on the effective temperature of \citet{CTN07}, $5081 \pm 50$~K,  and the radius estimate of $1.05 \pm 0.10 R_{\sun}$ derived from Doppler imaging \citep{DCS03}, compatible with the estimate derived from interferometry \citep[$0.96 \pm 0.06 R_{\sun}$; ][]{GMM11}.}

\section{Observational data} \label{sec:obsdata}

We use spectropolarimetric data collected in two different seasons with ESPaDOnS at the Canada France Hawaii Telescope \citep{DCL06}. Our data set totalizes 230 unpolarised (Stokes $I$) and 56 circularly polarized (Stokes $V$) spectra spread in three non-consecutive days in 2004, and 400 unpolarised and 98 circularly polarized spectra spread in four days (separated by 1-d gaps) in 2005. Observations cover wavelengths from 370 to 1,000~nm at a resolving power of 65,000. We refer to \cite{D03} for further details about the Stokes parameters acquisition with ESPaDOnS. We note that circularly polarised spectra typically require 4 sub-exposures, obtained at different orientations of the polarimeter retarders, to be combined in an optimal way to minimize potential spurious signatures \citep[see][for more details]{DSC97}.

Raw data frames are reduced with the Libre-ESpRIT package, which is optimised for ESPaDOnS \citep{DSC97}.  The spectra collected in 2004 have peak signal-to-noise ratios (SNRs) ranging from 75 to 191 (median 147), while in 2005 it ranged from 75 to 188 (median 158). Circularly polarised spectra with peak SNRs lower than $75$ were rejected in this work, corresponding to four sequences in the first season of observation (Nov/Dec 2004) and three sequences in the second one (Dec 2005). The complete log of our observations can be found in Tables~\ref{table:data1} and \ref{table:data2} (Appendix~\ref{sec:tables}). We use the ephemeris of \citet{VWV15} to compute the rotational cycle $E$ of each observation\footnote{We follow the  convention proposed by \cite{B00} and express timings in Terrestrial Time (TT) scale. }
 \begin{equation} \label{eq:ephemeris}
 \mathrm{HJED} \qq{=}  2445821.898291 + 0.5211833875\times E,
\end{equation}
where phase 0.5 corresponds to the primary eclipse of the system (i.e., when the WD is in front of the K2 star).

\subsection{Least-squares deconvolved profiles}

Least-Squares Deconvolution  \citep[LSD,][]{DSC97} is used to produce an average profile of photospheric lines of the K2 dwarf star, with the SNRs boosted by a factor of 30 from the peak SNR of the individual spectra (see Tables~\ref{table:data1} and \ref{table:data2}) with respect to an average spectral line. We constructed the line mask using the Vienna Atomic Line Database \citep[VALD; ][]{PKR95,K93} for an effective temperature $T_\mathrm{eff} = $~5,000~K and a surface gravity $\log g = 4.5$, in agreement with \citet{VWV15} (see Table~\ref{tab:paramsv471}). We chose to include in our absorption line list only lines deeper than $10\%$ to the continuum level ($I_\mathrm{c}$), resulting in roughly 6,000 atomic lines. The average line profile features a mean wavelength $\lambda = 625$~nm, a mean relative depth $d = 0.677$, and a mean effective Land\'{e} factor $w = 1.2$.

\section{Zeeman-Doppler Imaging of V471~Tau} \label{sec:modelling}
We analyze the time series of the spectropolarimetric data using ZDI to obtain information on the brightness and magnetic field distributions at the surface of the K2 dwarf of V471 Tau. First introduced by \citet{S89}, ZDI traces how distortions in Stokes $I$ and $V$ profiles retrieve maps of the stellar surface.

We use ZDI as described in a suite of papers \citep{DSP89,BDR91,DB97}, using the implementation of \citet{D01} and adopting a spherical harmonic decomposition for the magnetic field. In short, ZDI decomposes the stellar surface in a grid of $N$ cells (N being typically 10,000). Synthetic profiles are computed locally in each cell, using the analytical solution of Unno-Rachkovsky to the polarised radiative transfer equations in a Milne-Eddington model of atmosphere \citep{LDL04}. Then, local profiles from each grid cell are Doppler-shifted according to the radial velocity (RV) of the cell position and weighted by a linear limb-darkening law. The local RV of each cell is related to the geometry of the system (see Sec.~\ref{Section:input}) and to the rotation profile assumed at the stellar surface (either a simple solid-body rotation or a Solar-like square-cosine-type latitudinal differential rotation, see Sec.~\ref{sec:diff}). These local profiles are then combined into global synthetic Stokes $I$ and $V$ line profiles that are directly compared to the time series of the Stokes $I$ and $V$ LSD profiles.

In the next step, maximum-entropy principles are applied to both brightness and magnetic reconstructions \citep{SB84}. The code reconstructs surface maps with a conjugate gradient algorithm that searches for the lowest amount of information capable of fitting the data at a given $\chi^2$ level (similarly, one can minimize the $\chi^2$ at given information content using an iterative procedure). For brightness reconstructions, the principle is directly applied to the local brightness of the grid cells, while in magnetic reconstructions, the entropy is a function of the spherical harmonics coefficients \citep{DHJ06}. In this study, we truncate the spherical harmonic representation of the magnetic field at order $\ell=15$, which is enough to extract most spatial information available in the line profiles.

\subsection{System parameters}\label{Section:input}
We take advantage of the maximum-entropy fitting process to simultaneously estimate the orbital parameters describing the RV of the K2 dwarf of the binary system;  since the orbit of V471~Tau is circular, there are 3 such parameters, the semi-amplitude of the orbital motion of the K2 dwarf ($K_\mathrm{dK}$), the systemic velocity ($v_\gamma$), and the phase offset with respect to the ephemeris of Eq.~\ref{eq:ephemeris} ($\phi_0$). We perform a 3D search in the parameter space $K_\mathrm{dK}$, $v_\gamma$, and $\phi_0$ to find out how $\chi^2$ varies (at constant reconstructed information at the surface of the star) with these parameters. By fitting a 3D paraboloid around the minimum of the derived $\chi^2$ values, we compute the best estimates of the parameters and their uncertainties. An inspection of these parameters shows that slightly different systemic velocities (by about $3\sigma$) minimize phase-coherent patterns present in the residuals (observed minus modelled Stokes profiles) at both epochs. We adopt then $K_\mathrm{dK} = 149.3 \pm 0.2$~km/s and $v_\gamma = 35.0 \pm 0.1$~km/s. For the phase offset, we obtain for our Nov/Dec 2004 data set $\phi_0 = 0.0040 \pm 0.0002$  and for the Dec 2005 data $\phi_0 = 0.0035 \pm 0.0002$ (here a positive value in the phase offset, $\phi_0 > 0$, indicates a later conjunction when compared to the prediction from ephemeris in Eq.~\ref{eq:ephemeris}). Both values of $\phi_0$ agree within the error bars.

Likewise, once the data are corrected for the orbital motion, we search for the projected rotational velocity $v\sin(i)$ that allows our synthetic profiles to match best the times series of Stokes $I$ LSD profiles. For both data sets, the line-of-sight projected equatorial rotation velocity associated with the lowest $\chi^2$ is consistent within $2.5\sigma$ with \citet{VWV15}, i.e., $v\sin(i) = 89.30\pm 0.11$~km/s.

\section{Surface maps} \label{sec:maps}
We carry out reconstructions of brightness and magnetic maps of the K2 dwarf of V471~Tau for both data sets using the orbital and stellar parameters obtained in the previous section. As we discuss in Sec.~\ref{sec:diff}, differential rotation is detected at the surface of the K2 dwarf star, and we take it into account in the imaging process.

\subsection{Brightness maps}
\begin{figure*}
	\centering
	\includegraphics[width=\textwidth]{figs/dynamic_2004.png}
	\includegraphics[width=\textwidth]{figs/dynamic_2005.png}
    \caption{Dynamical spectra of the intensity flux (Stokes $I$) of the K2 dwarf of V471 Tau for our Nov/Dec 2004 (top) and Dec 2005 (bottom) data sets. From left to right, we show the observed LSD profiles, the modeled observations, and the residuals (i.e., observations minus model). LSD and modeled spectra were divided by the synthetic line profile of an unspotted star to emphasize spot signatures. We multiplied the residuals by a factor of $10^4$ for display purposes.}
    \label{fig:dynamic}
\end{figure*}

Figure~\ref{fig:dynamic} shows the dynamical spectra of Stokes $I$ profiles (for the individual profiles see Appendix~\ref{sec:StokesAppendix}). These dynamical spectra exhibit obvious signatures crossing the spectral line from the blue wing to the red wing, generated by surface brightness features being carried across the visible hemisphere as the star rotates. The few low-level features still present in the residuals, for instance, the blue and red vertical bands located at $\pm v\sin{i}$, reflect the fact that the width of the LSD profile slightly varies with phase as a result of the finite integration time (blurring the spectral lines at conjunction phases, i.e., when they move fastest, and thereby making them slightly wider). However, the typical amplitude of these residuals ($\sim\negmedspace10^{-3}$) is low enough not to cause any significant spurious features in the reconstructed images.

The reconstructed brightness maps are shown in Figure~\ref{fig:brightness}. In 2004, the spot distribution exhibited a cool polar spot off-centered towards phase 0.15, extending down to a colatitude of $\sim\negmedspace50\degr$. We likewise identify in 2005 a cool polar cap, although it presents a higher contrast with the quiet photosphere and is now off-centered towards phase 0.35. Besides, both spot maps show a partial ring of low-contrast warm features encircling the polar region with a latitudinal extension of $\sim\negmedspace40\degr$. The ring disrupts at phase 0.5, corresponding to the face turned to the WD companion. Overall, the polar spot distributions exhibit similar structures but with a phase shift of $0.20 \pm 0.05$ from 2004 to 2005 (a result also noticeable in the dynamical spectra of both epochs Fig.~\ref{fig:dynamic}). We find that, in 2004, cool spots and warm plages covered $8\%$ and $6\%$ of the stellar surface, respectively, whereas, in 2005, the spot coverage was $10\%$ for cool spots and $7\%$ for warm plages. The increase in spot coverage between the two epochs possibly relates to the denser phase coverage of our 2005 data.

\begin{figure}
    \centering
    \includegraphics[width=.4\textwidth]{figs/brightness_2004.pdf}
    \includegraphics[width=.4\textwidth]{figs/brightness_2005.pdf}
     \caption{Brightness maps obtained in Nov/Dec 2004 (top panel) and Dec 2005 (bottom panel). The logarithm of the relative brightness is shown in colors, with brown shades representing cool spots and blue shades depicting bright plages. In each polar representation, concentric circles denote regions of iso-latitude plotted in steps of $30\degr$ from the inner to the outermost circle. Ticks outside the polar representation indicate the rotation phase of the observations used to recover the maps.}
    \label{fig:brightness}
\end{figure}

\subsection{Magnetic topology} \label{sec:magtop}
Observed Stokes $V$ profiles, with the ZDI fit down to a unit reduced $\chi^2$ level, are shown in Appendix~\ref{sec:StokesAppendix} (Figs.~\ref{fig:sv2004} and \ref{fig:sv2005}). The topology of the K dwarf's large-scale magnetic field is depicted in Fig.~\ref{fig:magtop}. We found a maximum radial field strength of 250~G in 2004 and 230~G in 2005, while the root-mean-square magnetic field was $\sim\negmedspace160$~G. In Nov/Dec 2004, the magnetic field topology shows a complex configuration with 60$\%$ of the magnetic energy reconstructed in modes with $\ell \geq 4$, whereas, in 2005, the energy stored in these modes dropped to 30$\%$. The remaining energy is mostly stored in the dipolar ($\ell = 1$) and octupolar ($\ell = 3$) components, but  quadrupolar components totalling up to $\sim\negmedspace10\%$ of the magnetic energy are also present in the reconstructed topology. In 2004, the magnetic field featured a $-90$~G dipole tilted by $20\degr $ to the rotation axis towards phase $0.08 \pm 0.03$. In 2005, the intensity of the dipole component was $-105$~G and the $64\degr$ tilt goes towards phase $0.41 \pm 0.03$. To assess the uncertainties of the image reconstruction, we performed 120 magnetic inversions at each epoch from bootstrapped data sets constructed by randomly choosing spectra from the original data, allowing for duplicates to match the original size of the sample \citep[e.g., see ][]{WSC17,WSG18}. Table~\ref{mag_tab} lists the main properties of the reconstructed large-scale magnetic topology along with the standard deviations obtained in the bootstrapping analysis.

\begin{figure*}

    \centering
    \includegraphics[width=\textwidth]{figs/mag_2004.pdf}
    \includegraphics[width=\textwidth]{figs/mag_2005.pdf}
    \caption{Polar view of magnetic field topology for Nov/Dec 2004 (top panels) and Dec 2005 (bottom panels). From left to right, the columns show respectively the radial, azimuthal (i.e., toroidal), and meridional components of the large-scale magnetic field (with concentric circles and ticks as in Fig.~\ref{fig:brightness}). Magnetic field strengths are saturated at $350$~G, with red shades representing positive values and blue shades negative values.}
    \label{fig:magtop}
\end{figure*}

\begin{table}
\addtolength{\tabcolsep}{-3pt}
	\centering
	\caption{Magnetic field proprieties of the K dwarf star at Nov/Dec 2004 and Dec 2005. B$_\mathrm{rms}$ is the root-mean-square field, B$_\mathrm{dip}$ is the dipolar strength, and E$_\mathrm{pol}$ is the fractional energy in the poloidal field. E$_{\ell = 1}$, E$_{\ell = 2}$, E$_{\ell = 3}$ and E$_{\ell \geq 4}$ are, respectively, the fractional energies of the dipolar, quadrupolar, octupolar, and multipolar (defined as $\ell \geq 4$) components.}
	\label{mag_tab}
	\begin{tabular}{lcccccccc}
	          \hline
 Date &  B$_\mathrm{rms}$ & B$_\mathrm{dip}$& $\theta_\mathrm{dip}$ & E$_\mathrm{pol}$ & E$_{\ell = 1}$  &  E$_{\ell = 2}$  & E$_{\ell = 3}$  &  E$_{\ell \geq 4 }$   \\
  & (G) & (G) & $\left(\degr \right)$ & $(\%)$ & $(\%)$ & $(\%)$ & $(\%)$ & $(\%)$ \\
 \hline
 2004 & $160 \pm 3$ & $-90 \pm 20$& $ 20 \pm 10$ & $ 70 \pm 5$ & $ 15 \pm 6$ & $ 10 \pm 2$ & $ 15 \pm 2$ & $ 60 \pm 7$ \\
 2005 & $160 \pm 1$ & $-105 \pm 5$ & $ 64 \pm 5$ & $ 60 \pm 2$ & $ 45 \pm 3$ & $ 10 \pm 1$ & $ 15 \pm 2$ & $ 30 \pm 2$\\
	         \hline
	\end{tabular}
\end{table}

\section{Surface differential rotation}\label{sec:diff}

Thanks to the ability of ZDI to recover spatial information from sets of phase-resolved spectropolarimetric observations,  it is possible to retrieve information on differential rotation at the star's surface by finding out the recurrence rates of reconstructed features as a function of latitude. The procedure we use here, first described by \citet{DMC00}, takes into account an \textit{a priori} dependence of the angular velocity with latitude in the image reconstruction process. We adopt a Sun-like differential rotation law, written as:
\begin{equation}
    \Omega(\theta) = \Omega_\mathrm{eq} -\mathrm{d}\Omega \cos^2(\theta),
\end{equation}
where $\theta$ is the colatitude, $\Omega_\mathrm{eq}$ is the angular velocity at the equator, and $\mathrm{d}\Omega$ is the difference between $\Omega_\mathrm{eq}$ and the angular velocity at the pole. Because this functional form depends on two free parameters, the reconstructed tomography likewise relies on the choice of $\Omega_\mathrm{eq}$ and $\mathrm{d}\Omega$. The differential rotation parameters, therefore, correspond to the set of parameters leading to the images with the lowest information content (similar to the procedure outlined in Sec.~\ref{Section:input}).

Figure~\ref{fig:dr} shows $\chi^2$ maps in the $\Omega_\mathrm{eq}$ -- $\mathrm{d}\Omega$ plane for reconstructions using Stokes $I$ (left column) and Stokes $V$ (right column) signatures. We again assume a simple paraboloid approximation for the $\chi^2$ maps close to the minimum to determine the optimal differential rotation parameters (circles) and their associated error bars \citep[see Eqs. 2 and 3 in ][]{DCP03}. We summarise the differential parameters found for each case in Table~\ref{diff_table}. The four detection reveal equatorial regions spinning faster than the polar ones, which corresponds to a solar-like shear. We additionally list in Table~\ref{diff_table} the colatitude $\theta_\mathrm{c}$ at which the system rotates with the orbital period and the colatitude and rotation rate of the spots' gravity center ($\theta_\mathrm{s}$ and $\Omega_\mathrm{s}$).

For an independent check that the error bars on the differential rotation parameters we derived are reliable, we constructed ten bootstrapped data sets for both epochs of observation (Nov/Dec 2004 and Dec 2005). We repeated the procedure described in this section for the bootstrapped data sets and derived ten differential rotation measurements for each Stokes profile. We find that the mean values of $\Omega_\mathrm{eq}$ and $\mathrm{d}\Omega$ agree within error bars with the values quoted in Table~\ref{diff_table} and that the dispersion on these two parameters is consistent with the error bars derived from the $\chi^2$ maps. Moreover, the mean value of the error bars derived from the $\chi^2$ maps is similar to those quoted in Table~\ref{diff_table}.

\begin{figure*}
        \centering
	\includegraphics[width=.47\textwidth]{figs/dr_i_chipot_2004.pdf}
	\includegraphics[width=.47\textwidth]{figs/dr_v_chipot_2004.pdf} \\
	\includegraphics[width=.47\textwidth]{figs/dr_i_chipot_2005.pdf}
	\includegraphics[width=.47\textwidth]{figs/dr_v_chipot_2005.pdf}
    \caption{$\chi^2$ maps in the differential rotation plane obtained with reconstructions of the brightness distribution (left panels) and with reconstructions of the magnetic topology (right panels). Top plots show the results for Nov/Dec 2004 data and bottom ones for Dec 2005 data. Confidence levels up to 5~$\sigma$ (11~$\sigma$ for Stokes $I$ data collected in 2005) are shown in colors and are computed with respect to the $\chi^2$ minima. The circles and 1-$\sigma$ error bars indicate the center of the $\chi^2$ distribution given by Eqs. 2 and 3 in \citet[][]{DCP03}, with the measurements of 2004 shown in red and those of 2005 in blue. Note that we repeated the 4 differential rotation measurements in each panel to aid comparisons.}
    \label{fig:dr}
\end{figure*}

\begin{table*}
	\centering
	\caption{Differential rotation parameters derived from our Nov/Dec 2004 and Dec 2005 observations. Columns 2 - 7 show results obtained from Stokes $I$ data and columns 8 - 13 those obtained with Stokes $V$ data. Equatorial rates $\Omega_\mathrm{eq}$ are listed in columns 2 and 8, while differential rotation rates $\mathrm{d}\Omega$ are shown in columns 3 and 9 along with $1\sigma$ error bars for both quantities. For future reference, we also provide the colatitude of co-rotation ($\theta_\mathrm{c}$), the colatitude of the gravity centre of the spot/magnetic distribution \citep[$\theta_\mathrm{s}$;][]{DMC00}, and the rotation rate at this colatitude ($\Omega_\mathrm{s}$). The number of data points ($n$) used in each image reconstruction is provided in columns 7 and 13. }
	\label{diff_table}
	\begin{tabular}{lccccccccccccc}
	          \hline
	                    & \multicolumn{6}{c}{Stokes $I$ / Brightness reconstruction}  & & \multicolumn{6}{c}{Stokes $V$ / Magnetic field reconstruction}       \\
	       	 Epoch & $\Omega_\mathrm{eq}$  & $\mathrm{d}\Omega$  & $\theta_\mathrm{c}$ & $\theta_\mathrm{s}$ & $\Omega_\mathrm{s}$  & $n$ &  & $\Omega_\mathrm{eq}$  & $\mathrm{d}\Omega$   & $\theta_\mathrm{c}$ &  $\theta_\mathrm{s}$ & $\Omega_\mathrm{s}$ & $n$ \\
		            &   (rad/d)  & (mrad/d) &  ($\degr$)  & ($\degr$) &  (rad/d) &  &  &    (rad/d)    & (mrad/d)   &  ($\degr$)   &  ($\degr$)    &   (rad/d)        &     \\
		\hline
		 2004  & $ 12.106 \pm 0.001$   & $ 100 \pm 5 $ & $44 \pm 2$ &   $65$  & $12.088$ & 27572 &  & $ 12.116 \pm 0.008$   & $ 129 \pm 23 $ & $46 \pm 8$  &  $57$  & $12.078$ & 6344 \\
		 2005  & $ 12.091 \pm 0.001$   & $ 73 \pm 2 $ & $46 \pm 1$ &   $57$  & $12.069$ & 48800 &  & $ 12.083 \pm 0.004$   & $ 48 \pm 12 $ & $40 \pm 15$ &  $59$  & $12.070$ & 11590 \\
	         \hline
	\end{tabular}
\end{table*}

\section{Balmer lines} \label{sec:halpha}
The H$\alpha$ line is often used as tracer of magnetic activity in stars. Figure~\ref{fig:ha} displays the dynamical spectra of H$\alpha$ for both observing epochs. We find that in both data sets, H$\alpha$ is modulated with orbital phase, being weakest at phase 1.0, i.e., when the WD is behind the K2 star, and strongest at phase 0.5, i.e., when the WD is in front of the K2 star. The equivalent width reveals a peak-to-peak modulation amplitude of about 1.6~{\AA} with a maximum emission reaching $-0.5$~{\AA} in Nov/Dec 2004 and $-0.6$~{\AA} in Dec 2005 (see Fig.~\ref{fig:haeq}). A similar modulation pattern is also visible in the core of other active lines (see Appendix~\ref{sec:lines}).

By comparing the dynamical spectra of H$\alpha$ at both epochs, we detect an additional emission component moving in phase with the WD star in the 2004 data set. A Gaussian fit to the spectral signature around phase 0.75 yields an equivalent width of about $-0.33$~{\AA} and a full width at half maximum of  $1.95$~{\AA}. We interpret this extra emission as a prominence trapped in the magnetic field of the K2 dwarf. From the semi-amplitude of its signature in the dynamic spectrum ($210~\pm~38$~km/s in the rest frame of the K2 star), we can infer that the corresponding plasma is located at a distance of $2.35 \pm 0.43~\mathrm{R_\star}$ from the center of the K2 star towards the WD, i.e., at a distance of only $1.23~\mathrm{R_\star}$ from the WD. Although less obvious, a similar signature can also be identified in H$\beta$ after the removal of the stellar contribution (here assumed to be well represented by the prominence free spectra obtained in 2005 -- see Fig.~\ref{fig:activitylines}). Figure~\ref{fig:hb} shows the resulting spectra, where regions within $\pm v\sin{i}$ were masked to emphasize the prominence signature. From the isolated profile around phase 0.75, we estimate an H$\beta$ equivalent width of about $-0.096$~{\AA}, implying a Balmer H$\alpha$ to H$\beta$ decrement factor of 3.4.

\begin{figure}
    \centering
    \includegraphics[width=0.4\textwidth]{figs/dynha2004.png}
    \includegraphics[width=0.4\textwidth]{figs/dynha2005.png}
    \caption{Dynamical spectra of H$\alpha$ line, in the rest frame of the K2 dwarf, for observations in late 2004 (top) and Dec 2005 (bottom). The vertical dashed lines correspond to the stellar rotational broadening of $\pm v\sin(i)$. Sine waves of amplitudes $150$~km/s (center of mass), $210$~km/s (prominence position), and $320$~km/s (WD position) are over-plotted on the 2004 dynamical spectrum. Weak features from telluric lines, noticeable by its sinusoidal behavior, remained after the removal procedure. }
    \label{fig:ha}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.45\textwidth]{figs/Halpha_all.pdf}
        \caption{Rotational modulation in the H$\alpha$ equivalent width. Red symbols shown the data collected in Nov/Dec 2004 and the blue ones the data from Dec 2005.}
    \label{fig:haeq}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.4\textwidth]{figs/prominencehb2004.png}
        \caption{Dynamical spectra of H$\beta$ in 2004 after the removal of the stellar contribution (see text). Sine waves match the ones described in Fig.~\ref{fig:ha} and regions within $\pm v\sin{i}$ were masked for clarity.}
    \label{fig:hb}
\end{figure}

\section{Discussion} \label{sec:disc}
We analyzed spectropolarimetric data of the close-binary system V471~Tau acquired in Nov/Dec 2004 and Dec 2005. Photospheric lines of the K2 dwarf companion were identified after correcting for the orbital motion of the system (Sec.~\ref{Section:input}). We used ZDI to characterize the surface distribution of brightness and magnetic features at the surface of the K2 dwarf from the shapes and rotational modulation of Stokes $I$ and $V$ profiles. We discuss below the main results of this paper and how they contribute to the understanding of the various physical effects we aimed at studying.

\subsection{Spot and magnetic structures}\label{sec:disc_maps}
We applied ZDI to our Nov/Dec 2004 and Dec 2005 data sets to reconstruct the brightness and magnetic maps at the surface of the K2 dwarf component of V471~Tau.  Our brightness maps exhibit a cool off-centered polar spot and a hot ring-like structure at low-latitude. The brightness maps we reconstruct resemble previous results obtained with similar techniques in 1992/1993 \citep{RHJ95} and 2002 \citep{HAS06}, especially at high latitudes. This implies that polar spots are long-lived at the surface of the K2 dwarf, as they are on the single-star analog AB~Dor \citep[e.g.,][]{DCS03}. The spot coverage we derive (14$\%$ and 17$\%$ in Nov/Dec 2004 and Dec 2005 respectively) are in good agreement with what is expected from photometry (in the range 15–25$\%$, see Sec.~\ref{sec:paramsv471tau}) suggesting that most of the brightness spots generating photometric fluctuations in V471~Tau are large enough to be detected and resolved by Doppler imaging.

The magnetic maps we obtained in this work are the first reconstructions achieved for the K2 dwarf V471~Tau (Fig.~\ref{fig:magtop}). The unsigned average magnetic flux at the surface of the star is $\sim\negmedspace200$~G, including a $\sim\negmedspace100$~G dipole component inclined at 20–60$\degr$ to the rotation axis. We note changes in the field topology between the 2 epochs, e.g., an increase in the strength of the toroidal component (from 30 to 40$\%$ of the reconstructed magnetic energy) and in the fractional energy of the dipolar component (from 15 to 45$\%$). However, we caution that such changes may at least partly reflect the improved phase coverage in our second observing session.

\subsection{Differential rotation and angular momentum distribution}\label{sec:fluctdiff}
We detect differential rotation at the surface of the K2 dwarf at both epochs of observation (Table~\ref{diff_table}). In 2004, we found that the brightness and magnetic maps are sheared by $\mathrm{d}\Omega=100\pm5$ and $129\pm23$~mrad/d, respectively; whereas, in 2005, these shears dropped to $\mathrm{d}\Omega=73\pm2$ and $48\pm12$~mrad/d. These results differ from that of \citet{HAS06}, who found an almost solid body rotation ($\mathrm{d}\Omega = 1.6\pm6$~mrad/d) for the star in 2002, already offering some tentative evidence for fluctuations in the surface shear on a short timescale ($\sim\negmedspace2$-yr). Furthermore, this finding reflects those of \citet{DCP03} who identified similar fluctuations in the single-star analog AB~Dor.

Our results show at both epochs that the magnetic topology suffers a different shear than the brightness distribution, which may reflect that brightness and magnetic features are anchored at different depths within the convective zone.  Following \citet{DCP03}, we propose to interpret the temporal fluctuations in the surface differential rotation of the K2 dwarf in terms of redistribution of angular momentum within the convective zone as the star progresses on its activity cycle.  Assuming angular momentum conservation in the convective zone, they found that variations in $\Omega_\mathrm{eq}$ and $\mathrm{d}\Omega$ should be correlated. For instance, in stars with a Sun-like angular rotation profile (varying with latitude and independent of radius), the correlation shows up as:
\begin{equation}
    \Omega_\mathrm{eq} =  0.2 \mathrm{d}\Omega + \Omega_0,
\end{equation}
where $\Omega_0=2\pi/P_\mathrm{rot}$. On rapid rotators however, where angular rotation is constant along cylinders according to Taylor-Proudman theorem, the correlation takes the following form:
\begin{equation}
    \Omega_\mathrm{eq} = \lambda \mathrm{d}\Omega + \Omega_0,
\end{equation}
where $\lambda$ is a parameter related to the second and fourth-order moment of the fractional radius. For AB~Dor and the K2 component of V471 Tau, $\lambda$ is expected to be about $0.52$ \citep{DCP03}.

\begin{figure}
	\centering
	\includegraphics[width=0.46\textwidth]{figs/diff_rot.pdf}
    \caption{Differential rotation at the K2 dwarf's surface obtained with our Nov/Dec 2004 (red) and Dec 2005 (blue) data sets with $\pm 1$–$\sigma$ level provided. The measurement of \citet{HAS06} in 2002 ($\Omega_\mathrm{eq}=12.0547\pm0.001$~rad/d and $\mathrm{d}\Omega = 1.6\pm6$~mrad/d) is the green cross and the angular velocity if the star was rotating as a solid body at the orbital angular velocity of the binary system, i.e., $\Omega = 2\pi/P_\mathrm{orb}$, the black dot.  A linear fit of these six quantities (dashed line) returns the following relationship  $\Omega_\mathrm{eq} = (0.48 \pm 0.02) \mathrm{d}\Omega + (12.056 \pm 0.002)$~rad/d. For comparison, we include shear measurements reported for the analog AB~Dor \citep[purple circles;][]{DCP03,JDC07}, after scaling the x-axis to the same rotation rate so that measurements for both stars can be compared.}
    \label{fig:angmom}
\end{figure}

Figure~\ref{fig:angmom} shows the various existing estimates of differential rotation obtained so far for the K2 dwarf of V471~Tau. The linear fit to these values (in rad/d), including a solid-body rotation at the orbital period, yields the following trend:
\begin{equation} \label{eq:fitdiff}
\Omega_\mathrm{eq} = (0.48 \pm 0.02) \mathrm{d}\Omega + (12.056 \pm 0.002)~\mathrm{rad/d}.
\end{equation}
The slope we get, $\lambda = 0.48 \pm 0.02$, is consistent with expectations that rotation is constant on cylinders in stars rotating as fast as the K2 dwarf, as expected from the Taylor-Proudman theorem.

In previous theoretical studies on close binaries, tides were claimed to be capable of quenching surface differential rotation \cite[e.g.,][]{S81,S82}. However, the shears reported in this work, as well as those of the HD~155555 binary system \citep[][]{DHC08}, do not confirm this conclusion. In particular, our result indicates that surface differential rotation in close binary stars is not specific to young stars like HD~155555. We also note that temporal fluctuations in the surface differential rotation of the K2 dwarf of V471~Tau tend to be larger than those reported for AB~Dor \citep[see purple circles in Fig.~\ref{fig:angmom};][]{DCP03,JDC07}, which may reflect the impact of tidal forces on dynamo processes. Nevertheless, it is noteworthy that in both stars shear variations follow the same trend in the $\Omega_\mathrm{eq} - \mathrm{d}\Omega$ plane (Fig.~\ref{fig:angmom}), which is further evidence in favor of our interpretation that angular rotation is constant along cylinders in the convective zone of these two similar active stars.

\subsection{Origin of ETV in V471~Tau}
We consider the different models proposed to explain the ETVs observed in the V471~Tau system in light of our results. Whereas the existence of a third body to explain ETVs is not completely ruled out, its existence currently seems unlikely \citep{HSP15}.

In the \citet{A92} mechanism, period modulations are an outcome of a cyclic redistribution of angular momentum induced by a dynamo mechanism operating within the active companion. The exchange of angular momentum throughout the activity cycle affects the star's oblateness, causing a modulation in the quadrupole moment and, therefore, changing the gravity in the orbital plane. When the quadrupole moment of the K2 star increases, the WD approaches the companion and the system's orbital period decreases to conserve angular momentum (and vice versa).

Several authors questioned whether the Applegate mechanism could explain the ETVs of close binaries  \citep{L05,L06,VSB18}, since the cyclic exchange of angular momentum required in this model demands large shear fluctuations to explain typical period modulations \citep[e.g., $\Delta P/P_\mathrm{orb}\simeq 8.5 \times 10^{-7}$ for V471~Tau, cf.][]{L20}. In particular, for post-common envelope binary systems in which the active companion has a radiative core, \citet{VSB18} found that a relative differential rotation $\mathrm{d}\Omega/\Omega \lesssim 1\%$ (compatible with our results range $0.4-1.1$ per cent) can only lead to period variations $\lesssim\negmedspace10^{-7}$, thus making it unlikely to occur in V471~Tau. However, because our observations were undertaken during a phase in the ETV cycle when the observed minus predicted eclipse timings are maximum, and therefore when the orbital period is more or less nominal (i.e., equal to the mean orbital period quoted in Table~\ref{tab:paramsv471}), our measurements would have sampled intermediate values of the shear (expected to scale with the orbital period) rather than the maximum possible value for the K2~dwarf in the context of the Applegate framework. Surface shears larger by almost an order of magnitude  than those we detected are thus expected to be present when the orbital period is minimum if the Applegate mechanism is to explain the reported orbital period fluctuations, which remains to be investigated with more observations.

An alternative mechanism requiring weak shear fluctuations ($\mathrm{d}\Omega/\Omega \sim 0.004\%$) was recently suggested to operate in V471~Tau \citep{L20}. Like in the Applegate model, the new mechanism proposes that ETVs are caused by gravity changes in the orbital plane, with the main difference being the nature of the variations. \citet{L20} showed that if the K2 dwarf harbors a stationary non-axisymmetric magnetic field (instead of the dynamo modulated field invoked in the Applegate model), then an internal torque is introduced in the system forcing the magnetic structures to oscillate. Two distinct solutions were found for the magnetic structures whose orientation changes with respect to the star, a libration around phase 0.5 or circulation at a constant rate. In V471~Tau, \citet{L20} found a $70$-yr modulation period for the magnetic field for both libration and circulation models to account for the observed orbital period fluctuations of 35-yr. These models required magnetic field strengths at the base of the convective zone in the range of 8 to 17~kG, implying surface fields of a few kG. In order to asses whether this model is quantitatively compatible with observations, additional data similar to those analysed in this work must be acquired over the time span of the orbital period modulation.

\subsection{Magnetic activity and prominences}
We find that in our spectra of V471~Tau, H$\alpha$ exhibits a behaviour similar to that reported in the literature \citep[e.g.,][]{YRS91,BLM91,VWR02,KRJ07}, i.e. strongest when the WD is in front of the K2 star. \citet{RBY02} suggested that tidal forces in the binary system are able to trigger active longitudes at the surface of the K2 dwarf where the activity is enhanced with respect to the other side of the star. Potential field extrapolation of the surface radial field can help us visualize the magnetic field topologies obtained in our study (Fig.~\ref{fig:maglines}). Indeed, in 2005, the dipole field component, which largely dictates the overall geometry of the corona at a distance of a few stellar radii, seems to be oriented towards the azimuth of the WD. However, in 2004, nothing obvious shows up from the distribution of field lines. Admittedly, these potential field extrapolations are likely to be no more than rough descriptions of the magnetosphere, since we did not take in to account the gravitational impact of the WD.

\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{figs/fieldlines_withWD_2004.pdf}
	\includegraphics[width=0.4\textwidth]{figs/fieldlines_withWD_2005.pdf}
    \caption{Potential field extrapolations of the large scale radial field obtained with ZDI reconstructions in 2004 (top panel) and 2005 (bottom panel). Field lines are seen at rotational phase 0.75. The local strength of the magnetic field (G) at the surface of the star is shown in colours and open/closed lines are depicted in yellow/black. For this extrapolation, we assumed a source surface located 3.5~$R_\star$ beyond which all field lines break open, e.g., under the impact of centrifugal forces. The WD star (black circle) and the prominence detected in 2004 (red circle) are also shown. Field lines crossing the prominence are coloured in magenta.}
    \label{fig:maglines}
\end{figure}

Figure~\ref{fig:schematic} shows the schematic view of the system. In our Nov/Dec 2004 observations, the H$\alpha$ dynamical spectrum reveals the presence of a prominence at a stable location in the rotation frame over the seven rotation cycles of our observing run. Similar results are reported in previous studies on the activity of V471~Tau \citep[e.g.,][]{YRS91,RBY02}. We find the prominence to be located at $2.35 \pm 0.43~\mathrm{R_\star}$ from the centre of the K2 dwarf, farther away towards the WD than the center of mass of the system (located at $1.679\pm0.004~\mathrm{R_\star}$ from the centre of the K2 dwarf) and the Lagrange point L1 (located at $1.84\pm0.02~\mathrm{R_\star}$). Therefore, closed loops of the stellar magnetosphere likely extend out to few stellar radii and can maintain the slingshot prominence for at least 7 rotation cycles \citep{SHM96,JCD20}. Indeed, we can identify from the potential field reconstruction in 2004 some closed field lines that reach, and are potentially able to confine, the observed prominence (see Fig.~\ref{fig:maglines}).
\begin{figure}
	\centering
	\includegraphics[width=0.45\textwidth]{figs/system.pdf}
    \caption{Schematic view of the binary system V471~Tau in the presence of a prominence. Distances to the center of mass  and to the Lagrange points $L_1$ and $L_3$ are indicated by CM, L1, and L3 ($=-2.58~\mathrm{R_\star}~\vu{x}$), respectively. The size of the binaries and the prominence were kept in scale, where the prominence was approximated by a spherical blob with radius $\ell \sim 0.50 R_\star$ (see text).}
    \label{fig:schematic}
\end{figure}

The spectral signature of the prominence indicates a Balmer decrement $I(\mathrm{H}\alpha)/I(\mathrm{H}\beta) \approx 3.4$. Although the assumption of optically thin emission is not strictly true given the Balmer decrement we measure, we nonetheless use it to derive a lower estimate for the mass density of the detected prominence, whose emission is mostly due to radiative recombination of hydrogen atoms. We assume that the prominence is a spherical blob with radius $l = 0.50~R_{\star}$ (computed from the FWHM of H$\alpha$) and a temperature of 5,000~K. From the prominence flux $f_\mathrm{H\alpha} = 2.1 \times 10^{-13}~\mathrm{erg}~\mathrm{s}^{-1}\mathrm{cm}^{-2}$, we use the mass density expression derived by \citet{SHM96} (their Eq.~3) to compute $\rho = 4\times10^{-14}~\mathrm{g}~\mathrm{cm^{-3}}$. Accordingly, we can use the volume of the blob to derive an estimate of the prominence mass of $6\times 10^{18}$~g. Our mass estimation is three to four orders of magnitude greater than large prominences in the Sun \citep[$\approx 10^{15}$~g,][]{HBB06} and one order of magnitude grater than the mass range derived for the prominences around AB~Dor \citep[2-10$\times 10^{17}$~g, e.g., ][]{CR89,CDE90}.

We estimate the minimum magnetic tension in the loop necessary to hold the prominence through the inequality
\begin{equation} \label{eq:tension}
    \frac{B^2}{4\pi R_c} \geq \rho g_\mathrm{eff},
\end{equation}
where $B$ and $R_\mathrm{c}$ are respectively the field strength and the curvature radius at the top of the loop, $\rho$ is the prominence density, and $g_\mathrm{eff}$ is the effective gravity acting on the gas accounting also for the centrifugal acceleration \citep[see][]{SHM96}. We follow previous authors and adopt a typical field curvature radius of $R_\mathrm{c} = 0.30~\mathrm{R_\star}$  \citep[e.g.,][]{DMC00}, keeping in mind that if the loop is further bended a lower field strength would be required to hold the prominence. The effective gravity inside the prominence features a sharp gradient, ranging from $\va{g_\mathrm{eff}} = 2.5$~m/s$^2~\vu{x}$ in the prominence regions closest to the L1 point up to $\va{g_\mathrm{eff}} = 485$~m/s$^2~\vu{x}$ in the prominence regions facing the WD, with an intermediate value of $\va{g_\mathrm{eff}} = 132$~m/s$^2~\vu{x}$ in the prominence central regions. With $\rho = 4 \times 10^{-14}~\mathrm{g}~\mathrm{cm}^{-3}$, we find that the $B$ field requested to hold the prominence material ranges from 2 to 22~G
depending on whether the magnetic loop crosses the orbital plane on the sides of the prominence that are closest to or farthest from the K2 star, and to a strength of 11~G at the center of the prominence. These field estimates tend to be larger than the values of the extrapolated field (see Fig.~\ref{fig:maglines}) we derive within the prominence (ranging from 8 to 2~G for the sides of the prominence that are closest to or farthest from the K2 star, respectively), especially in the prominence section closest to the WD. This suggests that the prominence region closest to the L1 point is the most stable against centrifugal ejection, unless the field lines at the top of the loop are bent to a larger extent than what we assumed here. Our results therefore suggest that the observed prominence is indeed likely sustained against centrifugal ejection by a slingshot mechanism, as already documented for several CVs in the past \citep[][]{SHM96}.

As the WD is known to be magnetic we can expect magnetosphere from both system stars to interact. Previous studies explored possible signatures from reconnection events at the magnetosphere interface \citep{PCS93,LWC96,NS99}. In the light of our result and given the dipole field of 350~kG reported for the WD \citep{SSB98,SBL12}, we can estimate the location of the magnetosphere interface between both components of V471~Tau, which we find to be located at a distance of about $3.07~\mathrm{R_\star}$ from the K2 star and $0.516~\mathrm{R_\star}$ from the WD (given the dipole field of $\sim\negmedspace100$~G found on the K2 star). From this magnetospheric interaction, we can expect increased activity at the surface of the K2 dwarf when the WD is in front of the K2 star (phase 0.5), in qualitative agreement with what is observed (see Fig.~\ref{fig:haeq}).

\section{Summary}
In our work, we reconstructed for the first time the large-scale magnetic field at the surface of the K2~dwarf and reported new detection of its surface differential rotation. The strong shear we found demonstrates that the K2~dwarf can be differentially rotating and is not always rotating as a solid body, as previous observations may have suggested \citep{HAS06}. Moreover, our results provide evidence for temporal variations in the surface shear of the K2~dwarf, making it even more similar to its single-star analog AB~Dor. Our findings highlight the importance of further investigation of the V471~Tau system in order to understand the impact of binary companions on the dynamo processes operating in the convective layers of low-mass stars. In particular, as differential rotation is expected to amplify toroidal magnetic fields, new spectropolarimetric observations of V471 Tau should allow us to study a potential connection between temporal variations in differential rotation and the underlying dynamo processes (e.g., through observations of polarity changes in the magnetic topology).

Furthermore, additional magnetic maps will probe the long-term effects of the K2~dwarf's magnetism on the V471~Tau system, invoked as the potential cause of the observed ETVs \citep[e.g.,][]{A92,L20}. As a follow-up study, we plan to monitor the system at a number of different phases of the ETV modulation cycle, in particular those at which the orbital period gets close to its minimum and maximum values, expected to correspond to the phase of the maximum and minimum shear in the framework of the Applegate mechanism. Monitoring the temporal evolution of the large-scale magnetic topology of the K2 dwarf of V471~Tau will also allow us to improve our understanding of the prominence stability and lifetime and determine their impact on the overall rate at which such prominences participate in the angular momentum loss of the whole system.

\section*{Acknowledgements}
We acknowledge funding from the European Research Council (ERC) under the H2020 research $\&$ innovation  programme (grant agreement $\#740651$ New-Worlds).

\section*{Data Availability}
This paper includes data collected by the ESPaDOnS spectropolarimeter,
which is publicly available from the Canadian Astronomy Data Center (program IDs: 05BF14 $\&$ 04BD50).

\bibliographystyle{mnras}


text:
\section{Preliminaries}\label{sec:Introduction}

\subsubsection*{Binary Search Trees}

A \emph{binary tree} $T$ contains of a finite set of \emph{nodes}, with one
node designated to be the \emph{root}. All nodes have a \emph{left} and a
\emph{right} \emph{child} pointer, each leading to a different node. Either or
both children may be \emph{missing}, and we denote a missing child by
\texttt{null}. Every node in $T$, save for the root, has a single
\emph{parent} node of which it is a child. (The root has no parent.) The
\emph{size} of $T$ is the number of nodes it contains, and is denoted $|T|$.

There is a unique path from $\Root(T)$ to every other node $x$ in $T$, called
the \emph{access path for $x$ in $T$}. If $x$ is on the access path for $y$
then we say $x$ is an \emph{ancestor} of $y$, and $y$ is a \emph{descendent} of
$x$. We refer to the subtree comprising $x$ and all of its descendants as the
subtree rooted at $x$. Nodes thus have \emph{left} and \emph{right subtrees}
rooted respectively at their left and right children. (Subtrees are
\emph{empty} for \texttt{null} children.) The \emph{depth} of the node $x$,
denoted $d_T(x)$, is the number of edges on its access path. Its
\emph{right-depth} is the number of right pointers followed, and its
\emph{left-depth} is the number of left pointers followed.

In a \emph{binary search tree}, every node has a unique \emph{key}, and the
tree satisfies the \emph{symmetric order} condition: every node's key is
greater than those in its left subtree and smaller than those in its right
subtree. The binary search tree derives its name from how its structure enables
finding keys. To find a key $k$ initialize the current node to be the root.
While the current node is not \texttt{null} and does not contain the given key,
replace the current node by its left or right child depending on whether $k$ is
smaller or larger than the key in the current node, respectively. The search
returns the last current node, which contains $k$ if $k$ is in the tree and
otherwise \texttt{null}.

The \emph{lowest common ancestor} of $x$ and $y$ in $T$, denoted $\LCA_T(x,y)$,
is the deepest node shared by the access paths of both $x$ and $y$. Since the
root is a common ancestor of any pair of nodes in $T$ and $T$ is finite,
$\LCA_T(x,y)$ exists and is well defined. Furthermore
$\min\{x,y\}\le\LCA_T(x,y)\le\max\{x,y\}$.

To \emph{insert} a new key $k$ into a binary search tree $T$, we first do a
search for $k$ in $T$. When the search reaches a missing node, we replace this
node with a node containing the key $k$. (Inserting into an empty tree makes
$k$ the root key.)

\subsubsection*{Rotation}

Binary search trees are the canonical data structure for maintaining an ordered
set of elements, and are building blocks in countless algorithms. Perhaps the
most attractive feature of binary search trees is that the number of
comparisons required to find an item in an $n$-node binary search tree is
$O(\log n)$, provided that that the tree is properly arranged, which is good in
theory and practice. However, without exercising care when inserting nodes, a
binary search tree can easily become unbalanced (for example when inserting
$1,2,\dots,n$ in order), leading to search costs as high as $\Omega(n)$. Thus,
binary search trees require some form of maintenance and restructuring for good
performance.

\begin{figure}
\centering
\includegraphics[width=\columnwidth,trim={.15in 1.3in .25in
2in},clip]{./Rotation.pdf}
\caption{Rotation at node $x$ with parent $y$, and reversing the effect
by rotating at $y$.}\label{fig:Rotation}
\end{figure}

We will employ a restructuring primitive called \emph{rotation}. A rotation at
left child $x$ with parent $y$ makes $y$ the right child of $x$ while
preserving symmetric order. A rotation at a right child is symmetric, and
rotation at the root is undefined. (See Figure \ref{fig:Rotation}). A rotation
changes three child pointers in the tree.

Rotations were first employed in ``balanced'' search trees, which include AVL
trees \cite{AVL_TREES}, Red-Black trees \cite{RED_BLACK_TREES}, weight-balanced
trees \cite{WEIGHT_BALANCED_TREES}, and more recently weak AVL trees
\cite{WEAK_AVL_TREES}. These trees augment nodes with bits that provide rough
information about how ``balanced'' each node's subtree is. Whenever an item is
inserted or deleted, rotations are performed to restore invariants on the
balance bits that ensure all search paths have $O(\log n)$ nodes. While
balanced searched trees are not the focus of this work, they were progenitors
for the main algorithm of interest.

\subsubsection*{Splay}

The Splay algorithm \cite{SPLAY_JOURNAL} eschews keeping track of balance
information, replacing it with an intriguing notion: instead of adjusting the
search tree only after insertion and deletion, Splay modifies the tree after
\emph{every} search.

\begin{figure}
\centering
\includegraphics[width=\columnwidth]{./HorizontalSplaySteps.pdf}
\caption{A splaying step at node $x$. Symmetric variants not shown. Triangles
denote subtrees.}\label{fig:SplaySteps}
\end{figure}

The algorithm begins with a binary search for a key in the tree. Let $x$ be the
node returned by this search. If $x$ is not \texttt{null} then the algorithm
repeatedly applies a ``splay step'' until $x$ becomes the root. A splay step
applies a certain series of rotations based on the relationship between $x$,
its parent, and its grandparent, as follows. If $x$ has no grandparent (i.e.
$x$'s parent is the root), then rotate at $x$ (this case is always terminal).
Otherwise, if $x$ is a \emph{left} child and its parent is a \emph{right}
child, or vice-versa, rotate at $x$ twice. Otherwise, rotate at $x$'s parent,
and then rotate at $x$. Sleator and Tarjan \cite{SPLAY_JOURNAL} assigned the
respective names \emph{zig}, \emph{zig-zag} and \emph{zig-zig} to these three
cases. The series of splay steps that bring $x$ to the root are collectively
called to as \emph{splaying at $x$}, or simply \emph{splaying $x$}. The three
cases are depicted in Figure
\ref{fig:SplaySteps}.

The \emph{cost} of splaying a single item $x$ in $T$ is defined to be
$d_T(x)+1$.\footnote{We absorb the search cost into the rotations.} If
$X=(x_1,\dots,x_m)$ is a sequence of requested keys in $T$ then the cost of
splaying $X$ starting from $T$ is defined as $m+\sum_{i=1}^m d_{T_{i-1}}(x_i)$,
where $T_0=T$, and for $1\le i \le m$, we form $T_i$ by splaying $x_i$ in
$T_{i-1}$. To perform \emph{insertion splaying}, insert a key into the tree and
then splay the newly created node. The cost of an insertion splay is the cost
splaying the new node.

While splaying individual items can cost $\Omega(n)$, the \emph{total} cost of
splaying $m$ requested items in a tree of size $n>0$ is $O((m+n)\log n)$.
Hence, the worst case cost of a splay operation, \emph{amortized} over all the
requests, is the same as any balanced binary search tree. This is perhaps
surprising for an algorithm that keeps no record of balance information.

What makes Splay truly remarkable is how it takes advantage of ``latent
structure'' in the request sequence, and provides more than simple
``worst-case'' guarantees. As just one example, if $t_X(i)$ is the number of
different items accessed before access $i$ since the last access to item $x_i$
(or since the beginning of the sequence if $i$ is the first access to $x_i$),
then the cost to splay $X$ starting from $T$ is $O(n\log n
+\sum_{j=1}^m\log(t_X(j)+1))$ \cite{SPLAY_JOURNAL}.\footnote{Note that $O(\log
n)$ amortized cost per splay is a corollary of this.} (This is called the
``working set'' property.) Thus, Splay exploits ``temporal locality'' in the
access pattern.

Splay simultaneously exploits ``spatial'' locality, as shown by the following
theorem (originally conjectured in \cite{SPLAY_JOURNAL}) that we will use later
on:
\begin{theorem}[Dynamic Finger \cite{DYNAMIC_FINGER_1,DYNAMIC_FINGER_2}]
\label{thm:DynamicFinger}
Let the \emph{rank} of $x$ in $T$, denoted $r_T(x)$, be the number of nodes in
$T$ whose keys are less than or equal the key in $x$. The cost of splaying
$X=(x_1,\dots,x_m)$ starting from $T$ is $O(|T|+m+\DF_T(X))$, where
$\DF_T(X)\equiv\sum_{i=2}^m \log_2(|r_T(x_i)-r_T(x_{i-1})|+1)$.
\end{theorem}

In fact, the properties of Splay inspired the authors of \cite{SPLAY_JOURNAL}
to speculate on a much stronger possibility: that Splay's cost is always within
a constant factor of the ``optimal'' way of executing the requests. Formally,
an \emph{execution} $E$ for $(X,T)$ comprises the following. Let $T_0=T$, and
for $1\le i\le m$, we perform some number $e_i\ge 0$ of rotations starting from
$T_{i-1}$ to form $T_i$, followed by a search for $x_i$. The \emph{cost} of
this execution is $\sum_{i=1}^m(1+e_i+d_{T_{i-1}}(x_i))$. The \emph{optimal
cost} $\operatorname{OPT}(X,T)\equiv\min\{\operatorname{cost}(E)\mid\text{$E$
executes $(X,T)$}\}$. The following conjecture has spawned a great deal of
related research (see \S\ref{sec:RelatedWork}):

\begin{conjecture}[Dynamic Optimality \cite{SPLAY_JOURNAL}]
$\operatorname{cost}_{\text{splay}}(X,T)=O(\operatorname{OPT}(X,T))$.
\end{conjecture}

The conjecture remains open. In fact, there is no sub-exponential time
algorithm \emph{whatsoever} that is known to compute, even to within a constant
factor, the cost of an optimum binary search tree execution for an instance.
There are several known lower bounds \cite{GEOMETRY,WILBER}, none known to be
tight (though some conjectured to be).

\subsubsection*{Pattern-Avoidance}

For simplicity, we restrict subsequent discussion to \emph{permutation} request
sequences (i.e. no key is requested twice). By \cite{PATTERN_AVOIDANCE}, any
algorithm that achieves optimal cost on all permutations can be extended to an
algorithm that is optimal for all request sequences.

An auxiliary question to determining if Splay (or any other algorithm) is
dynamically optimal is: ``what class(es) of permutations have optimum
executions with `low' cost?'' This issue is not a mere curiosity, as almost
every permutation of length $n$ has optimal execution cost $\Theta(n\log n)$
\cite{BST_EXECUTION_ENCODINGS}, a bound achieved by any balanced search tree.
Thus, in the absence of insertions or deletions, adjusting the tree after every
access only gives an advantage on a small subset of ``structured'' request
sequences. In addition, these structured request sequences provide candidate
counter-examples to dynamic optimality. In this work, we focus on certain
\emph{pattern-avoiding} permutations: those that do not contain any
subsequences of a specified type. More formally:\footnote{The following
definitions and theorems are taken from \cite[Chapter 1.3]{KOZMA_THESIS},
almost verbatim.}

 Two permutations $\alpha=(a_1,\dots, a_n)$ and
$\beta=(b_1,\dots, b_n)$ of the same length are \emph{order-isomorphic}
if their entries have the same relative order, i.e. $a_i<a_j\iff
b_i<b_j$. For example, $(5,8,1)$ is order-isomorphic to $(2,3,1)$. A
sequence $\pi$ \emph{avoids} a sequence $\alpha$ (or is called
\emph{$\alpha$-avoiding}) if it has no subsequence that is order-isomorphic
with $\alpha$. If $\pi$ is $\alpha$-avoiding then all subsequences of $\pi$ are
$\alpha$-avoiding. We use $\pi\setminus\alpha$ as shorthand for ``an
(arbitrary) permutation $\pi$ that avoids $\alpha$.'' Both preorders and
postorders may be characterized as pattern-avoiding permutations:

\begin{lemma}[Lemma 1.4 from \cite{KOZMA_THESIS}] For any permutation $\pi$: \item
\begin{thmenum}
\item\label{lem:Preorders231} $\pi=\Preorder(T)$ for some binary search tree $T$ $\iff\pi$ avoids $(2,3,1)$.
\item\label{lem:Postorders312} $\pi=\Postorder(T)$ for some binary search tree $T$ $\iff\pi$ avoids $(3,1,2)$.
\end{thmenum}
\end{lemma}
\begin{proof}[Sketch]
For preorders, Kozma builds a bijection between binary search trees and
$(2,3,1)$-avoiding sequences, and uses a simple argument by contradiction to
show preorders avoid $(2,3,1)$ \cite{KOZMA_THESIS}. The proof for postorders is
a nearly symmetric variation of this argument.
\end{proof}

\section{Related Work}\label{sec:RelatedWork}

The first result about Splay's behavior on pattern-avoiding request sequences
was the \emph{sequential access} theorem \cite{SEQUENTIAL_ACCESS}: the cost of
splaying the nodes of $T$ in order is $O(|T|)$. This is a special case of a
corollary\footnote{A priori, the traversal conjecture follows from dynamic
optimality \emph{conditioned} on Splay being optimal with low ``additive
overhead.'' The authors recently proved that this corollary is actually
\emph{unconditional} \cite{A_NEW_PATH}.} of dynamic optimality:
\begin{conjecture}[Traversal \cite{SPLAY_JOURNAL}]
There exists $c>0$ for which the cost of splaying $\Preorder(T)$ starting from
$T'$ is at most $c|T|$ for all pairs of binary search trees $T, T'$ with the
same keys.
\end{conjecture}
Theorem~\ref{thm:InsertionSplayingPreorders} and \cite{SPLAY_PREORDER} is
another special case, when $T=T'$. In \S\ref{sec:MainResults} we prove a new
special case: when $T$ is $\alpha$-weight balanced.

Interest in the behavior of binary search tree algorithms on ``structured''
request sequences was revived by Seth Pettie's analysis of the performance of
Splay-based deque data structures using Davenport-Schinzel sequences
\cite{DAVENPORT_SCHINZEL}, and his later reproof of the sequential access
theorem via the theory of forbidden submatrices \cite{FORBIDDEN_SUBMATRIX}.

This analysis was later adapted to and greatly extended for another binary
search tree algorithm, colloquially known as ``Greedy,'' that was first
proposed as an \emph{off}-line algorithm independently by Lucas
\cite{CANONICAL_FORMS} and Munro \cite{MUNRO_GREEDY}. Greedy is widely
conjectured to be dynamically optimal, and is known to have many of the same
properties of Splay, including the working set \cite{GREEDY_ACCESS_LEMMA} and
dynamic finger \cite{GREEDY_DYNAMIC_FINGER} bounds.

Greedy was later recast as an on-line algorithm in a ``geometric'' view of
binary search trees \cite{GEOMETRY}. This geometric view of Greedy is
especially amenable to forbidden submatrix analysis. In
\cite{PATTERN_AVOIDANCE}, Chalermsook et. al. show that Greedy has
nearly-optimal run-time on a broad class of pattern-avoiding permutations.
Moreover, they demonstrate that if Greedy is optimal on a certain class of
``non-decomposable'' permutations then it is dynamically optimal. Chalermsook
et al.'s analysis was later simplified in \cite{SIMPLER_PATTERN_AVOIDANCE}.

\section{Insertion Splaying Preorders and Postorders}\label{sec:MainResults}

If $\pi=(p_1,\dots,p_n)$ is a permutation then the \emph{insertion tree for
$\pi$}, denoted $\BST(\pi)$, is the binary search tree obtained by starting
from an empty tree and inserting keys in order of their first appearance in
$\pi$.
\begin{lemma}\label{lem:AncestorPrecedence}
If $x$ is a proper ancestor of $y$ in $\BST(\pi)$ then $x$ precedes $y$ in
$\pi$.
\end{lemma}

\begin{proof}
Let $\pi_{\prec y}$ denote the prefix of $\pi$ containing the elements preceding
$y$. By construction, $y$ is inserted as a child of some node $z$ in
$\BST(\pi_{\prec y})$. Every proper ancestor of $y$ is an ancestor of
$z$, thus $x\in\BST(\pi_{\prec y})$. Hence, $x$ precedes $y$.
\end{proof}

Insertion splaying $\pi$ has the same cost as splaying $\pi$ starting from
$\BST(\pi)$.\footnote{This is because the manner in which Splay restructures
the access path is independent of nodes outside the path.} For the purposes of
analysis we will assume that, initially, every node in $\BST(\pi)$ is marked as
\emph{untouched}. An insertion splay marks the node as \emph{touched}, and then
splays the node. The touched nodes form a connected subtree containing the
root, called the \emph{touched subtree}. The untouched nodes form subtrees each
of which contains no touched node. Call an untouched node with a touched parent
a \emph{sub-root}. The subtrees rooted at sub-roots have identical structure in
both the splayed tree and $\BST(\pi)$. By Lemma \ref{lem:AncestorPrecedence},
the next node to be touched is always a sub-root.

For $1\le i\le n$, form $T_i$ by touching and then splaying $p_i$ in $T_{i-1}$,
where $T_0=\BST(\pi)$ starts with all nodes untouched. At any time we define
the \emph{potential} to be the twice the number of touched nodes that are
ancestors of sub-roots, and we define $\Phi_i$ to be the potential of $T_i$.
The \emph{amortized} cost of splaying $p_i$ in $T_{i-1}$ is defined as
$c_i=t_i+\Phi_i-\Phi_{i-1}$, where $t_i$ denotes the actual cost. By a standard
telescoping sum argument, the cost of insertion splaying $\pi$ is $\sum_{i=1}^n
t_i = \sum_{i=1}^n c_i + \Phi_0 - \Phi_n$ \cite{AMORTIZED_TIME}. Since
$\Phi_0=\Phi_n=0$, an upper bound on amortized cost provides an upper bound on
the actual cost.

Pattern-avoidance provides certain information about both $\BST(\pi)$ and about
which sub-root can be touched next. We exploit this information in the next two
sections.

\subsubsection*{Preorders}

There are no restrictions on the possible structure of preorder insertion trees
as $\BST(\Preorder(T))=T$.\footnote{In fact, this property is shared by
\emph{any} permutation $\pi$ for which every node in $T$ appears in $\pi$
before those in its left and right subtrees.} However, the manner in which
sub-roots are chosen is particularly simple.

\begin{lemma}\label{lem:PreorderSubroots}
If $\pi\setminus(2,3,1)=(p_1,\dots,p_n)$ is a preorder then, for $1\le i\le n$,
$p_i$ is the smallest sub-root of $T_{i-1}$, where all nodes begin untouched in
$T_0=\BST(\pi)$ and $T_i$ is formed by touching and splaying $p_i$ in $T_{i-1}$.
\end{lemma}

\begin{proof}
The statement is vacuously true for $i=1$. We prove for $i>1$ by contradiction,
as follows. Suppose $T_{i-1}$ has some sub-root $q$ that is smaller than $p_i$.
Since $q$ and $p_i$ are \emph{both} sub-roots in $T_{i-1}$, they are both
children of respective (though not necessarily distinct) nodes $a$ and $b$ in
$T_{i-1}$. Let $r=\LCA_{T_{i-1}}(a,b)$. Since $q\ne a$ and $p_i\ne b$, all of
$p_i$, $q$ and $r$ are distinct nodes in $T_{i-1}$, and furthermore $q<r<p_i$.
By Lemma \ref{lem:AncestorPrecedence}, $r$ precedes both $q$ and $p_i$ in
$\pi$, and by construction $p_i$ precedes $q$. We thus have $(r,p_i,q)$ is a
subsequence of $\pi$. But $(r,p_i,q)$ is order-isomorphic with $(2,3,1)$,
contradicting $\pi\setminus(2,3,1)$.
\end{proof}

\begin{figure}
\centering
\includegraphics[width=.85\textwidth]{./PreorderSubroots.pdf}
\caption{Possible locations for the next sub-root $x$ to be insertion splayed
in $\pi\setminus(2,3,1)$. The case on the left occurs when the next splayed
node has left-depth $0$, and the case on the right occurs when it has
left-depth $1$. Dashed nodes may or may not be present, and any number of nodes
may lie on the paths denoted by dashed lines.}\label{fig:PreorderSubroots}
\end{figure}

\begin{theorem}\label{thm:InsertionSplayingPreorders}
Insertion splaying $\Preorder(T)$ keeps each sub-root at left-depth at most $1$
and takes $O(1)$ amortized time per splay operation.
\end{theorem}

\begin{proof}
The theorem is trivial for the first insertion splay. The inductive hypothesis
is that every sub-root has left depth $0$ or $1$. Let $x$ be the next sub-root
to be splayed, and let $y$ and $z$ (either or both of which can be missing) be
its left and right children. Touching $x$ makes $y$ and $z$ into sub-roots.

Suppose $x$ has left depth $0$ before it is touched. Converting $x$ from
untouched to touched (without splaying it) increases the potential by at most
$2$ and gives the new sub-roots $y$ and $z$ left depths of $1$ and $0$,
respectively. (In this case they are the only two sub-roots.) Each splay step,
except possibly the last, is a zig-zig in which $x$ starts as a left child with
parent $p$ and grandparent $g$. After completing the zig-zig, $g$ is no longer
an ancestor of any untouched node, which decreases the potential by $2$. The
zig-zig also preserves the left depths of $y$ and $z$. ($y$ becomes the right
child of $p$.) No other sub-roots can increase left-depth, as $x$ is the
smallest sub-root. If the last splay step is a zig, the potential does not
change (although the length of the path to $y$ increases by $1$).

More complicated is the case in which $x$ has left depth $1$. Converting $x$
from untouched to touched (without splaying it) makes $y$ a sub-root of left
depth $2$ and $z$ a sub-root of left depth $1$. Let $w$ be the parent of the
ancestor of $x$ that is a left child. All other sub-roots are in the right
subtree of $w$, which is unaffected by splaying $x$. The splay of $x$ consists
of $0$ or more left zig-zigs, followed by a zig-zag (which can either
left-right or right-left), followed by zero of more left zig-zigs, followed
possibly by a zig. Each zig-zig reduces the potential by $2$ and preserves the
left depths of all sub-roots. The zig-zag does not increase the potential,
reduces the left depth of $y$ from $2$ to $1$, and that of $x$ from $1$ to $0$,
and preserves the left depth of $z$. Now $x$ has left depth $0$, and the
argument above applies to the remaining splay steps.

By Lemma \ref{lem:PreorderSubroots}, the next node to be splayed will be $y$
if present, otherwise $z$ if present, otherwise $w$ if present. All three of
these items have left-depth $0$ or $1$, hence an identical form to Figure
\ref{fig:PreorderSubroots}. Thus the hypothesis holds.

To obtain the constant factor, we observe that converting $x$ from untouched
to touched increases the potential by $2$. Each zig-zig step pays for itself:
it requires $2$ rotations, paid for by the potential decreasing by at least
$2$. The zig-zag requires $2$ rotations, and the zig requires $1$ rotation. If
the cost of a splay is the number of nodes on the splay path, equal to the
number of rotations plus $1$, we have an amortized cost of $6$ per splay.
\end{proof}

\subsubsection*{Postorders}

Postorder insertion trees are more restricted. A binary search tree $C$ is a
\emph{(left-toothed) comb} if the access path for $x\in C$ always comprises
some number $j\ge0$ of right children followed by some number $k\ge0$ of left
children. The nodes of $C$ are partitioned into \emph{teeth}, where every node
in the $i\textsuperscript{th}$ tooth has right-depth $i-1$. The shallowest node
in a tooth is called the \emph{head}. The insertion trees of postorders are
combs:

\begin{lemma}\label{lem:PostorderInsertionTrees}
If $\pi$ is a postorder then no left child in $\BST(\pi)$ has a right child.
\end{lemma}
\begin{proof}
By contradiction. Let $y$ be a left child in $\BST(\pi)$ with right child $z$,
and let $x=\Parent(y)$. As $z$ is $y$'s right child, $y<z$. Similarly, as both
$y$ and $z$ are in $x$'s left subtree, $y<z<x$. By Lemma
\ref{lem:AncestorPrecedence}, $y$ can be an ancestor of $z$ only if $y$
precedes $z$ in $\pi$, and similarly $x$ must precede $y$. Thus, $(x,y,z)$ is a
subsequence of $\pi$ that is order-isomorphic to $(3,1,2)$. By Lemma
\ref{lem:Postorders312}, $\pi$ is not a postorder.
\end{proof}

While postorder insertion trees are less varied than for preorders, there may be many postorders with a given insertion tree. This affords some amount of freedom for choosing different sub-roots.

\begin{lemma}\label{lem:PostorderSubroots}
Let $\pi\setminus(3,1,2)=(p_1,\dots,p_n)$ be a postorder with insertion tree sequence $T_0,T_1,\dots,T_n$. For $1\le i\le n$, $p_i$ is either: \item
\begin{enumerate}[label=\upshape(\alph*)]
\item\label{item:NewHead} The \emph{single} sub-root greater than
$\max\{T_{i-1}\}$ (if present), or
\item\label{item:CombHead} The largest sub-root smaller than $\max\{T_{i-1}\}$ (if present).
\end{enumerate}
\end{lemma}

\begin{proof}
The result is vacuous for $i=1,2$. If $p_i$ is case \ref{item:NewHead}, we
merely note that if $p_i$ is a new maximum then it must be the right child of
the largest node in $\max\{T_{i-1}\}$. There can be at most one sub-root in
this position. Hence, $p_i$ is unique.

For the sake of contradiction, suppose $p_i$ is not of the form in case
\ref{item:NewHead} or \ref{item:CombHead}, and let $q$ be the largest sub-root
smaller than $\max\{T_{i-1}\}$. By Lemma \ref{lem:AncestorPrecedence}, the
items of each tooth are added in decreasing order. As $q$ is not the head of
its tooth, its successor $r$ must be in $T_{i-1}$, and furthermore $r$ precedes
both $p_i$ and $q$ in $\pi$. By construction, $(r,p_i,q)$ is a subsequence of
$\pi$. Yet this subsequence is isomorphic to $(3,1,2)$ since $p_i<q<r$,
contradicting Lemma \ref{lem:Postorders312}.
\end{proof}

\begin{figure}
\centering
\includegraphics[width=.85\textwidth]{./PostorderSubroots.pdf}
\caption{Possible locations for the next sub-root $x$ to be insertion splayed
in $\pi\setminus(3,1,2)$. The case on the left occurs when the next splayed
node is less than the root, and the case on the right occurs when the next
sub-root is the new tree maximum. Dashed nodes may or may not be present, and
any number of nodes may lie on the paths denoted by dashed
lines.}\label{fig:PostorderSubroots}
\end{figure}

\begin{theorem}\label{thm:InsertionSplayingPostorders}
Insertion splaying postorders maintains the following invariants:
\begin{enumerate}
\item After each insertion splay, the path to every sub-root comprises $j\ge 0$
left pointers followed by $k\ge 0$ right pointers. (Furthermore, after the
first insertion, $k\ge 1$.)
\item The left-depth of every sub-root decreases from smallest to
largest.\footnote{The first two invariants dictate that the ancestors of
sub-roots form a \emph{right}-toothed comb.}
\item The splay operation takes constant amortized time.
\end{enumerate}
\end{theorem}

\begin{proof}
The base case is trivial. Lemma \ref{lem:PostorderSubroots} dictates that the
next splayed sub-root is either greater than all marked items, or is the
largest sub-root smaller than the tree root. Let $x$ be the next node to be
insertion splayed, $y$ its left child, and $z$ its right child (either or both
children may be missing).

Suppose $x$ is greater than the current tree root. Marking $x$ increases the
potential by $2$ and makes $y$ and $z$ new sub-roots. The splay operation
brings $x$ to the root by a sequence of left zig-zigs followed possibly by a
left zig (depending on whether the length of the access path is odd or even).
After each one of these zigs or zig-zigs, $y$'s left-depth remains $1$, and
$z$'s left depth remains $0$. Let $v$ be the root prior to the splay operation.
If the last splay step is a zig then the last splay operation increases the
left depth of $v$ and everything in its left subtree by either $1$ or $2$.
Since the left-depth of $x$ was $0$ and $x$ was the largest sub-root, the
inductive hypothesis ensures that all sub-roots had left-depth at least $1$
before the splay operation, and therefore at least $2$ afterward. Thus, when
$x$ becomes the root, the left-depths of each sub-root decrease from left to
right.

Otherwise, $x$ is the largest sub-root less than the root. Marking $x$ again
increases the potential by at most $2$. By Lemma
\ref{lem:PostorderInsertionTrees}, $x$ has no right child (see Figure
\ref{fig:PostorderSubroots}), so we only need to worry about its left child
$y$. Let $w$ be the last ancestor of $x$ that is a left child. Each left
zig-zig prior to the splay step involving $w$ maintains the left-depth of $y$
to be one greater than the left-depth of $x$. The splay step involving $w$ will
either be a left zig-zig or a left-right zig-zag, depending on the length of
the original path connecting $w$ to $x$. Regardless, immediately after the
splay step involving $w$, the ancestor of $y$ that is the left child of $x$ is
either the left child of $w$ or the left child of $w$'s parent. Since all the
sub-roots less than $y$ are in the left subtree of $w$, and thus have
left-depth greater than the left-depth of $y$, the invariant is restored, and
remains true after each right zig-zig or zig that brings $x$ to the root.

All that remains is showing constant amortized time. As noted before, marking
$x$ costs $2$. If $x$ is greater than the root then each left zig-zig, except
possibly the last, pays for itself, giving amortized cost of $4$. In the other
case, all splay steps except for the one involving $w$ and the one making $x$
the root pay for themselves, giving amortized cost at most $6$.
\end{proof}

\section{Balanced Trees}\label{sec:BalancedTrees}

Let $|x|$ denote the size of the subtree rooted at $x$. Following
\cite{WEIGHT_BALANCED_TREES}, we say $T$ is \emph{$\alpha$ weight balanced} for
$\alpha\in (0,1/2]$ if $\min\{|\Left(x)|, |\Right(x)|\}+1\ge
\alpha\cdot(|x|+1)$ for all $x\in T$, and write $T\in\BB[\alpha]$.

\begin{theorem}\label{thm:BalancedTraversal}
For any \emph{(fixed)} $0<\alpha\le 1/2$, if $S\in\BB[\alpha]$ and $T$ has the
same keys as $S$, then the cost of splaying $\Preorder(S)$ or $\Postorder(S)$
starting from $T$ is $O(|T|)$.
\end{theorem}

\begin{proof}
By Theorem \ref{thm:DynamicFinger}, it suffices to show that
$\DF_T(\Preorder(S))=O(|T|)$. Let
\begin{align*}
A_\alpha(n)\equiv\max\{\DF_T(\Preorder(S))\mid\text{$S\in\BB[\alpha]$ and $|T|=n$}\}.
\end{align*}

Recall that $\Preorder(S)=(\Root(S))\oplus\Preorder(L)\oplus\Preorder(R)$,
where $L$ and $R$ are the left and right subtrees of the root of $S$,
respectively. Notice that the rank differences between $\Root(S)$ and the first
item in $\Preorder(L)$, and between the last item in $\Preorder(L)$ and the
first item in $\Preorder(R)$, are at most $|T|$ by definition. Hence,
\begin{align*}
\DF_T(\Preorder(S)) \le \DF_T(\Preorder(L)) + \DF_T(\Preorder(R)) + 2\log_2(|T|+1).
\end{align*}

Observe that $(|L|+1)/(|S|+1)\in[\alpha,1-\alpha]$ since $S\in\BB[\alpha]$, and by definition $|R|<|S|-|L|$. Hence,
\begin{align*}
A_\alpha(n)=\max_{\alpha\le\beta\le1/2}\{A_\alpha(\beta\cdot n) + A_\alpha((1-\beta)\cdot n)\} + O(\log n).\footnotemark
\end{align*}
\footnotetext{Technically, since $|L|/|S|<(|L|+1)/(|S|+1)$, we need to pick $S$ sufficiently large for a given alpha, and offset the recurrence term by a corresponding constant. This does not asymptotically affect the result.}%
Akra-Bazzi's result \cite{AKRA_BAZZI} suffices to show $A_\alpha(n)=O(n)$ for
fixed $\alpha$. The proof for postorders is identical.
\end{proof}

\begin{remark}
In actuality, $A_\alpha(n)=O(f(\alpha)\cdot n)$ for some function $f$ of
$\alpha$. Unfortunately, the computation appears to be messy. We have declined
to do the necessary footwork, as we strongly suspect that, regardless,
$A_\alpha(n)$ does not tightly bound the cost of splaying these sequences.
\end{remark}

\begin{remark}
This result extends to any binary search tree algorithm that satisfies the
dynamic finger bound. Iacono and Langerman proved Greedy also has the dynamic
finger property \cite{GREEDY_DYNAMIC_FINGER}; their analysis does not
consider initial trees, however.
\end{remark}

\section{Remarks}\label{sec:GeneralPatterns}

Patterns that avoid $(2,1,3)$ are ``symmetric'' to those that avoid $(2,3,1)$:
if $\pi\setminus(2,1,3)$ then $\pi$ is the preorder of the mirror image of
$\BST(\pi)$. Similarly, patterns that avoid $(1,3,2)$ are symmetric to patterns
that avoid $(3,1,2)$. Thus, insertion splaying $\pi\setminus(2,1,3)$ and
$\pi\setminus(1,3,2)$ takes linear time.

The only other patterns of length three are $(3,2,1)$ and its symmetric
counterpart $(1,2,3)$. The pattern $(3,2,1)$ was explored in
\cite{PATTERN_AVOIDANCE}, where it was shown that Greedy executes
$(3,2,1)$-avoiding permutations in linear time starting from an
\emph{arbitrary} tree. In fact, they showed that executing
$\pi\setminus(k,\dots,2,1)$ takes time proportional to $n\cdot 2^{O(k^2)}$;
this is linear in $n$ for fixed $k$. These permutations are called
\emph{$k$-increasing} because they can be partitioned into $k-1$ disjoint
monotonically increasing subsequences \cite{PATTERN_AVOIDANCE}. They form the
natural generalization of \emph{sequential access}, which is the (unique)
permutation of the tree nodes that avoids $(2,1)$.

More general invariants can be derived about insertion tree structure and
sub-root insertion order based on pattern-avoidance. As one particularly
interesting example:

\begin{theorem}
If $\pi\setminus(k,\dots,2,1)$ then no node in $\BST(\pi)$ has left-depth more
than $k-2$, and the next sub-root inserted (without splaying) is always the
smallest sub-root with its given left-depth.
\end{theorem}

The proof is similar to Lemmas \ref{lem:PostorderInsertionTrees} and
\ref{lem:PostorderSubroots}. In particular, the insertion trees of
$(3,2,1)$-avoiding permutations look like the combs of postorder insertion
trees, except the teeth are rightward, instead of leftward paths.

For $k$-increasing sequences, the potential used for Theorems
\ref{thm:InsertionSplayingPreorders} and \ref{thm:InsertionSplayingPostorders}
needs modifications. The main issue is that in both of these cases, the
zig-zigs paid for themselves because the nodes knocked off the access path did
not have sub-root descendants. This structure no longer holds for
$(3,2,1)$-avoiding sequences, since we must splay the nodes of the teeth in
increasing order. The proof seems to require a generalization of the sequential
access theorem. It is possible that the notion of \emph{kernel trees} used by
Sundar in \cite{SUNDAR_DEQUE} for a potential-based proof of the sequential
access theorem could be useful.

\printbibliography

\end{document}

redpajama_set_name: RedPajamaArXiv