First Attempts in Deception Detection in HRI by using Thermal and RGB-D cameras

David-Octavian Iacob and Adriana Tapus

Abstract-A key factor of a successful Human-Robot Interaction (HRI) is the robot's ability to understand the messages transmitted by a human user, especially their nonverbal and paraverbal components. Our work focuses on the robot's ability to detect if a person is deceitful or honest, based on an evaluation of their physiological state and using only noninvasive techniques, such as thermal and RGB-D imaging. In particular, we currently study and evaluate several physiological manifestations during an experiment consisting of an interrogation conducted by a robot that follows a mockup crime, then correlate them with the truth values of the participants' answers. The first results are promising.

I. INTRODUCTION

Social robotics [START_REF] Duffy | Fundamental Issues in Social Robotics[END_REF] [START_REF] Hegel | Towards a Typology of Meaningful Signals and Cues in Social Robotics[END_REF] focuses on the development of robots that are able to interact as naturally as possible with humans. For a Human-Robot Interaction (HRI) to be natural and efficient, the robots should, first of all, be able to understand the messages sent by their human interlocutors as fast and as accurately as a human being. In this work, we do not focus on the verbal aspects of HRI, but on the nonverbal ones. Without the ability to understand the nonverbal and paraverbal components of the communication, the robots cannot fully understand the messages sent by their interlocutors. One of the consequences of a robot's inability to understand the nonverbal aspects of the communication is that humans could much more easily deceive a robot during an interaction than it would be to deceive another human in a similar human-human interaction.

Socially Assistive Robots (SAR) [START_REF] Feil-Seifer | Socially Assistive Robots[END_REF] focus on the social component of the interaction with humans in order to assist them. Their objective is to improve the quality of life of certain populations of users, such as people with neurological [START_REF] Malik | Emergence of Socially Assistive Robotics in Rehabilitation for Children with Cerebral Palsy: A Review[END_REF], motor [START_REF] Mataric | Socially Assistive Robotics for Stroke and Mild TBI Rehabilitation[END_REF], and/or cognitive impairments [START_REF] Tapus | Socially Assistive Robotic Music Therapist for Mantaining Attention of Older Adults with Cognitive Impairments[END_REF] in need of physical or psychological rehabilitation. Nonetheless, the latter might try to deceive the former the same way they might try to deceive a human assistant checking up on their progress (e.g., not taking their medication, not doing their physical therapy [START_REF] Matari | Socially assistive robotics for post-stroke rehabilitation[END_REF], not respecting certain interdictions or recommendations). Therefore, in order to improve the quality of the interaction, assistive robots need to be able to establish if the human users they interact with are deceitful adriana.tapus@ensta-paristech.fr

or trustworthy, at least up to the extent a human assistant is capable of doing so in similar scenarios.

Our work focuses on the development of noninvasive techniques that would allow a robot to detect deception, based on a series of physiological manifestations. Some of the physiological parameters are nonverbal cues, such as the head position and orientation, the eye openness and position, while others describe the cardiovascular and respiratory response of the organism to the psychological state of the individual, such as the heart rate, respiratory rate, and facial skin temperature variations. These parameters are monitored using noninvasive sensors, such as RGB-D [START_REF] Poh | Advances in Noncontact, Multiparameter Physiological Measurements using a webcam[END_REF] and thermal cameras [START_REF] Pavlidis | Thermal Facial Screening for Deception Detection[END_REF][10] [START_REF] Tsiamyritzis | Lie Detection -Recovery of the Periorbital Signal through Tandem Tracking and Noise Supression in Thermal Facial Video[END_REF]. The observations are then correlated with a known psychological state of the human user (either deception or trustworthiness). In order to measure, evaluate, and compare these manifestations, we have designed an experiment where human participants are enticed to deceive their robot interlocutor in order to get a reward.

The rest of the paper is structured as follows: section II presents an overview of the techniques that can be used in order to detect deception, section III describes the experimental setup we have used for our experiment, section IV describes the methodology used for data analysis, section V discusses the results of our work, and finally section VI concludes our paper.

II. DECEPTION AND ITS PHYSIOLOGICAL MANIFESTATIONS

The development of the polygraph [START_REF] Horvath | The reliability of Polygraph Examiner Diagnosis of Truth and Deception[END_REF] has shown that several physiological parameters can be correlated with deception, with various degrees of accuracy. We can distinguish between invasive measurement techniques, used to measure parameters such as the galvanic skin response (GSR) (or other measurements of the electro-dermal activity) [START_REF] Horvath | The reliability of Polygraph Examiner Diagnosis of Truth and Deception[END_REF][13] [START_REF] Ströfer | Deceptive Intentions: Can Cues to Deception Be Measured before a Lie Is Even Stated?[END_REF], heart rate and blood pressure [START_REF] Horvath | The reliability of Polygraph Examiner Diagnosis of Truth and Deception[END_REF][15], respiratory rate [START_REF] Horvath | The reliability of Polygraph Examiner Diagnosis of Truth and Deception[END_REF] or brain activity [START_REF] Lee | Lie Detection by Functional Magnetic Resonance Imaging[END_REF][17] and noninvasive measurement techniques, that can be used to monitor heart rate, using Fast Fourier Transform (FFT) video analysis [START_REF] Poh | Advances in Noncontact, Multiparameter Physiological Measurements using a webcam[END_REF] [START_REF] Garbey | Contact-Free Measurement of Cardiac Pulse Based on the Analysis of Thermal Imagery[END_REF], respiratory rate (FFT video analysis) [START_REF] Chauvin | Contact-Free Respiration Rate Monitoring Using a Pan-Tilt Thermal Camera for Stationary Bike Telerehabilitation Sessions[END_REF] [START_REF] Ruminski | Evaluation of respiration rate and pattern using a portable thermal camera[END_REF], voice audio frequencies [START_REF] Harnsberger | Stress and Deception in Speech: Evaluating Layered Voice Analysis[END_REF][22], facial expressions [START_REF] Barathi | Lie Detection based on Facial Micro Expression, Body Language and Speech Analysis[END_REF], or eye movements and blink rates [START_REF] Leal | Blinking During and After Lying[END_REF][24] [START_REF] Nourbakhsh | GSR and Blink Features for Cogni-tive Load Classification[END_REF].

The invasive physiological evaluation methods are, by far, the most accurate, since the measurement errors of the devices used in order to monitor these parameters are very low and allow a very accurate tracking of human physiological manifestations. According to [START_REF] Gaggioli | Beyond the Truth Machine: Emerging Technologies for Lie Detection[END_REF], polygraphs can now offer a reliability of 81% to 91%. Moreover, many of them have been used for several decades by prosecutors, investigators, and police forces as part of standardized lie detection techniques, therefore being considered the most advanced lie detection techniques available today. Nonetheless, even the best deception detection systems could provide false positive or false negative results, depending on each individual's physiological response, as well as their ability to control their physiological manifestations.

The main problem with the invasive lie detection techniques is the fact that some of them cannot be used in everyday human-robot interactions or human-human interactions, since they involve complex, fixed devices that cannot be carried around, while minimally-invasive techniques still mean that the person being monitored may simply remove the sensors placed on their body in order to avoid any form of deception detection. The heart rate [START_REF] Giles | Validity of the Polar V800 heart rate monitor to measure RR intervals at rest[END_REF] [START_REF] Sardini | Instrumented Wearable Belt for Wireless Health Monitoring[END_REF] and respiratory rate [START_REF] Sardini | Instrumented Wearable Belt for Wireless Health Monitoring[END_REF] can be evaluated using minimally invasive techniques, as well as the electro-dermal activity [START_REF] Nourbakhsh | GSR and Blink Features for Cogni-tive Load Classification[END_REF] (up to some extent, depending on the number and location of sensors). Blood pressure measurements [START_REF] Reid | Simulated Blood Pressure Responses in Lie-Detector Tests and a Method for Their Detection[END_REF] involve more encumbering sensors, while brain activity mapping [START_REF] Lee | Lie Detection by Functional Magnetic Resonance Imaging[END_REF] [START_REF] Simpson | Functional MRI Lie Detection: Too Good to be True?[END_REF] requires very complex and generally fixed, rooted systems.

Noninvasive lie detection has been already attempted in inter-human interaction scenarios [START_REF] Pavlidis | Thermal Facial Screening for Deception Detection[END_REF][10] [START_REF] Harnsberger | Stress and Deception in Speech: Evaluating Layered Voice Analysis[END_REF][22] [START_REF] Abouelenien | Analyzing Thermal and Visual Clues of Deception for a Non-Contact Deception Detection Approach[END_REF] with various degrees of success. Moreover, as previously shown, a series of noninvasive physiological measurements techniques have already been developed and they could be used for noninvasive lie detection. Nonetheless, to the best of our knowledge, there are no other works focusing on noninvasive physiological measurement based lie detection in HRI.

Therefore, one of the main objectives of this research is to develop purely noninvasive lie detection techniques that can easily be integrated in HRI scenarios, without interfering with the fluidity of the interaction. Any such device and method should therefore use sensors that can easily be integrated in a robot (if they are not already part of some robotic platforms) and should use algorithms that could evaluate if the interlocutor is deceitful or not with a minimum delay using computation power that can be provided by regular portable computers (laptops or embedded systems such as Raspberry PI and similar systems).

III. EXPERIMENTAL SETUP

The experiment we have designed has two main parts, that take place in different rooms: the mock-up crime and the interrogation. After the experiment is over, the participants are asked to fill a post-experimental questionnaire as well as a BIG5 [START_REF] Goldberg | An alternative description of personality: The big-five factor structure[END_REF] personality test. This experiment has been designed in order to collect relevant data and then to create a model based on the correlations that are found.

A. Part 1: The mock-up crime

After the participant was informed of the experiment, they enter the first room alone, then they locked the door. On a table inside the room, there is a sheet of paper containing the detailed experimental instructions for this part, a chocolate bar, and five objects: a red marker, a computer mouse, a e 20 bill, a book, and a mobile phone.

The participant is asked to choose 3 out of the 5 objects and hide them anywhere inside the room. Afterwards, the participant must take the chocolate bar, leave the room and not tell anyone, human or robot, what objects they have hidden inside the room, or otherwise they will not be able to keep the reward (the chocolate bar) at the end of the experiment. Afterwards, they are instructed to go straight to the interrogation room.

The room is secretly kept under video surveillance using a hidden wireless camera that allows the experimenter to know exactly what objects have been hidden by the participant before they start the second part of the experiment. This information is used in order to adapt the robot's interrogation speech.

B. Part 2: The interrogation

The participant enters the interrogation room, where an interrogator (a Pepper robot) sits behind a table. No humans can be seen inside the room, as the experimenter is hidden behind some curtains and oversees the experiment. The participant is therefore not aware of the experimenter's presence. The participant is invited by the robot to take a seat on the other side of the table, in front of the interrogator, who will then explain the interrogation procedure. The interrogation is recorded with the RGB-D and thermal camera system and consists of four phases:

1) General questions, not related to the experiment (e.g., Are you sitting down right now?). 2) Questions concerning the first part of the experiment to which the participant has no reason to lie (none is related to the 3 objects they have hidden). 3) Questions concerning the first part of the experiment to which the participant is enticed to lie (all of them are related to the 3 objects they have hidden). 4) The same exact general questions, not related to the experiment, asked in the first phase of the interrogation. The participant is told that they are free to choose whether they are honest or not throughout the interrogation. Therefore, the datasets obtained from each participant may have a variable number and distribution of truthful and dishonest answers, but the participants are given the control concerning what elements of information they are willing to disclose or not. This makes the interrogation process more realistic, even though the data is harder to analyze.

The interrogation begins with 11 preliminary questions, which the participant has no particular reason to answer dishonestly. Their purpose is to establish a baseline for the physiological parameters that are being monitored. Then the actual interrogation begins, with 11 questions concerning details of the first part of the experiment, but none related to the manipulation of the three objects the participant has hidden. The participants may choose to lie anyway, either because they do not want to tell anything about any aspect of the first part of the experiment or because they are unsure what details they have to hide in order to keep the reward.

The third part of the interrogation consists of 11 questions related to the three objects that have been hidden by the participant. This is the part of the interrogation where the participants must absolutely hide the truth in order to keep their reward. After this interrogation phase is done, the same 11 preliminary questions that have been asked in the beginning of the interrogation are being asked again. The purpose of this repetition of the preliminary question phase is to study if and to what extent the participants' physiological manifestations evolve back towards the baseline values. At the end of the experiment, the robot informs the participant if they can or cannot keep their reward. The participant is then invited to leave the room.

The interrogator (the Pepper robot) is remotely controlled by the experimenter supervising the interrogation behind the curtains. Several decisions have to be made based on the video footage provided by the hidden camera: which questions have to be included in the second and third part of the interrogation (based on the hidden objects) and whether the participant can or cannot keep their reward (based on the information revealed by the participant during the interrogation). Since the robot interrogator has no ability to detect lies so far, these decisions are taken by the human supervisor based on an assessment of the participant's answers.

Another key aspect of the interrogation procedure is that instead of using Pepper's default voice and text-to-speech, the questions are pre-recorded using the experimenter's voice, in both English and French. The main reason for this is that the default voice of the Pepper robot resembles that of a child, making it unsuitable for such interrogation scenarios. The questions (and the audio recordings used) are exactly the same for all the participants, except, of course, for the names of the hidden objects, which vary depending on what each participant has decided to hide, and the intonation used was as neutral and easy to understand as possible.

C. The questionnaires

Right after the experiment is over, the participants are asked to fill up a post-experimental questionnaire. It consists of a series of questions asking for feedback concerning the experiment, using a 7-points Likert scale. The postexperimental questionnaire's objective is to establish the perception of the participants with respect to several aspects:

• how much they wanted to keep the reward (as their desire to eat a chocolate bar might vary) • what was their perceived level of stress during each phase of the interaction (as stress can have similar physiological manifestations as deception) • whether they thought the robot interrogator knew the truth concerning what they have done in the first part of the experiment • whether they thought the robot interrogator was able to detect if they told the truth and if they lied (since they are not told whether the robot has this ability or not) • whether they considered the questions asked during the interrogation relevant in order to establish what they have done during the first part of the experiment.

The post-experimental questionnaires are either used to check if there is a certain bias in the experimental procedure (such as the reward not being enticing enough for the participants or the experimental procedure being to stressful) and also to correlate the physical manifestations of each participant to its perception of the experiment.

Another questionnaire that the participants are asked to fill up is the BIG5 personality test. For each of the five measured personality traits, the participants received a score from 1 to 5. In particular, we are interested in studying if their extroversion, their neuroticism, and their conscientiousness can be correlated with their physiological manifestations when trying to deceive the robot interrogator.

D. Participants

A number of 20 participants took part in this experiment. We have established, based on the post-experimental questionnaire as well as the BIG5 personality test, several subgroups, depending on each of the following parameters:

• gender: 13 male, 7 female • perceived stress (interrogation): 12 low, 8 high • desire to keep the reward: 4 low, 16 high • extroversion: 8 introverts, 12 extroverts • conscientiousness: 8 low, 12 high • neuroticism: 9 low, 11 high They were split based on the comparison of the value of each parameter with the average value (which is 3 in both the post-experimental questionnaire and the BIG5 personality test). A large majority of the participants, 17 out of 20, have a background in Technical Sciences, one in Theatre, one in Physics, and one in Medical Sciences.

IV. DATA ANALYSIS

A. Measurements

Two video cameras record the interrogation: an Asus Xtion RGB-D camera and an Optris PI640 thermal camera. They both provide a 640x480 output at 30 Hz and are connected to the data analysis computer used by the experimenter to supervise the experiment and to remotely control the robot. The video streams are being acquired using two ROS packages and then processed using a program developed in C++ using ROS and OpenCV. The software uses the CLM Face Tracker [START_REF] Baltrusaitis | Constrained Local Neural Fields for robust facial landmark detection in the wild[END_REF] to track 66 facial landmark points in the RGB-D frame, then a coordinate conversion function that transforms the RGB-D frame coordinates to thermal frame coordinates, using a calibration procedure based on the ROS camera calibration package. The application also monitors the video stream provided by the hidden camera in the first experimental room, allowing the experimenter to configure the robot's behaviour (which questions to ask) before the participant starts the interrogation.

Based on the facial landmark points detected using the CLM Face Tracker, several regions of interest (ROI) are being identified in the RGB frame, then their coordinates are being converted to thermal frame coordinates. The main regions of interest and the respective evaluated parameters are the following:

• the facial area: position, orientation, green colour component, depth (distance), temperature • the ocular and periocular areas: relative position, eye openness, relative temperature • the nose area: relative temperature The average values of each variable are being computed for each region of interest, while the relative positions and temperatures are computed with respect to the average values computed for the entire face. Each value, once computed, is logged to an individual stamped CSV (Comma Separated Variable) file, that is later used for post-experimental processing and analysis.

B. Analysis procedure

The logged data is analyzed post-experimentally, using Scilab / MATLAB scripts that process the CSV log files. Manual annotations register the key moments of the interrogation (beginning and end of each interrogation block), as well as the number of true and false answers for each interval. The annotations are used for data segmentation, so the evolution of each parameter can be correlated to the honesty of the participants.

For a given participant and evaluated parameter, we define 4 analysis intervals:

• preliminary questions (first run) • experiment-related questions: expected truths • experiment-related questions: expected lies • preliminary questions (second run)

If a participant has given more than 50% honest answers in a given interval, we consider that they have been honest during that interval and dishonest otherwise. If an answer is not clearly honest nor dishonest, it is marked as inconclusive and not taken into account. Therefore, for each of these four intervals we associate a "honesty" parameter that is either 1 or 0 depending on the percentage of truthful answers. The associated "honesty" parameter is 0 if the percentage of truthful answers is strictly lower than 50% and 1 otherwise.

All the recorded data was initially annotated by one of the authors. Afterwards, the data recordings of 3 random participants has been chosen for annotation by a second rater. The Cohen's kappa coefficient for inter-rater agreement had a value of κ = 0.921, which corresponds to almost perfect agreement. For each of these intervals, we compute the average value, the standard deviation and the slope of a linear interpolation of the data samples in the interval. For some of the variables (the facial green colour component, the nose temperature, and the eye vertical relative position) we also do an FFT analysis and extract the significant peaks in a given frequency band. Therefore, we can distinguish two types of variables, depending on whether we analyse their values or their representations in the frequency domain.

V. RESULTS

A. Statistical correlations

Based on the evaluation of the logged parameters, the physiological parameters we monitored are:

• estimated heart rate (facial green FFT) • estimated respiratory rate (nasal temperature FFT) • interocular and nasal relative temperature • eye vertical relative position • face distance with respect to the cameras Our first strategy was to analyse the data for each question/answer pair and correlate it with the truth value of each given answer. This approach was problematic for several reasons. First of all, due to the limited sampling rate of the video cameras (30 Hz), the FFT analysis used for the heart rate and respiratory rate detection algorithms needed windows of 30-60 seconds in order to have an usable frequency resolution:

1 beat per minute (BPM) for 60 seconds and 2 BPM for 30 seconds. On the other hand, some physiological manifestations, such as temperature variations due to vasodilation and vasoconstriction cannot be measured instantly, due to the body's response times and the skin's thermal inertia, which also implies a need for larger measurement windows. Among all the evaluated physiological parameters, the only one who has shown a statistical correlation was the estimated heart rate variability and only on three experimental subgroups: males, females, and participants with high neuroticism.

The heart rate was estimated based on a weighted mean of the most significant 5 frequency peaks of the FFT analysis in the 1...3 Hz frequency domain (corresponding to 60-180 BPM), since we assumed that the participants did not have a constant heart rate during the reference intervals and that the data measurements were prone to errors. The following graphs show the heart rate variability in Hz with respect to the first measurements interval (preliminary when the participants have mostly lied (column 0) or mostly told the truth (column 1). For each of these three experimental subgroups we have proven that there is a statistically significant difference in the heart rate variability with respect to the preliminary questions interval when saying the truth compared to when they were lying. The other variables that were analyzed, both on the entire group of 20 participants and on each individual subgroup have not shown any relevant statistical correlations according to standardized statistical tests. This can be caused by the low number of participants that have undertaken the experiment so far.

B. Questionnaire-based evaluation

The answers of the participants to the post-experimental questionnaire have been evaluated in order to establish whether the experiment was well designed or not. The participants' answers are on a Likert scale from 1 to 7, where 1 corresponds to "Strongly disagree", 7 corresponds to "Strongly agree" and 3 to "Neither agree nor disagree".

1) Did you want to keep the chocolate bar? Average: 5.50 (standard deviation of ±2.01)

2) Do you think the interrogator knew everything that you did inside the first room? Average: 5.05 (standard deviation of ±2.06) 3) Do you think the interrogator was able to detect when you were telling the truth and when you were not? Average: 3.96 (standard deviation of ±1.73) 4) Did you find the first part of the experiment stressful?

Average: 1.75 (standard deviation of ±1.29) 5) Did you find the interrogation stressful?

Average: 3.85 (standard deviation of ±2.00) 6) Did you feel threatened by the interrogator at any moment? Average: 2.8 (standard deviation of ±1.54) We can conclude that the reward was considered generally desirable by the participants, in spite of its low cost and of each participant's personal preference for chocolate. The participants were also generally convinced that the robot interrogator knew for a fact what objects they have hidden during the first part of the experiment, even though they were not as convinced that the robot had actual lie detection abilities.

Their evaluation of the stress level was also important. The first part of the experiment was considered totally not stressful, while the perceived level of stress during the interrogation was slightly above average. Moreover, the perceived level of threat from the robot interrogator was also slightly below average. This means that the interrogation could have been designed to be less stressful and/or threatening, in order to further reduce the risk of mistaking the physiological manifestations correlated to stress with those correlated to deception.

VI. CONCLUSIONS

The purpose of this research was to design an HRI scenario during which humans would be enticed to lie to a robot, therefore allowing us to evaluate their nonverbal and physiological manifestations using only noninvasive techniques and then to correlate the measurements with the honesty or dishonesty of their answers.

We have found statistical correlation between the truth value of the participants' answers for each of the measurement intervals and the estimated heart rate variability with respect to the first interval (preliminary questions) in three of the experimental subgroups (males, females, and participants with high neuroticism). In each of the three subgroups, the estimated heart rate was significantly higher when participants were mostly telling the truth than when they were mostly lying to the robot interrogator.

Nonetheless, the lower accuracy of the noninvasive measurements had a negative effect on our results meant that among all the monitored parameters the only one that was successfully statistically correlated with deception was the estimated heart rate variability. This was mostly due to the measurement errors induced by the measurement techniques and the hardware limitations, as well as by the fact that we did not restrict the natural movements of the participants in any way. This experiment can be considered in the wild, no restrictions, and no constraints were imposed to the participants.

In future research, we plan focusing on various ways of improving the quality of the data acquisition so that we are able to accurately monitor the other physiological manifestations that we tried to analyze during this experiment. Moreover, other noninvasive techniques will be integrated in order to evaluate more parameters that have been proven to be correlated with deception.

Moreover, we will also study whether there are any differences between the manifestations associated with deception when the participants lie to a robot or another human in identical interaction scenarios.

Fig. 1 .

 1 Fig. 1. Interrogation experimental setup

Fig. 2 .

 2 Fig. 2. Software architecture

Fig. 3 .

 3 Fig. 3. Example of a parameter's evolution (nasal area relative temperature)

The 7

 7 female participants have shown an estimated mean heart rate variability of -0.004 Hz (-0.24 BPM) when lying and of 0.2 Hz (+12 BPM) when telling the truth, with F(1,19)=5.87 and p=0.0256. The data was normally distributed and analyzed with the ANOVA test.

Fig. 4 .

 4 Fig. 4. Female participants: heart rate variability

Fig. 5 .

 5 Fig. 5. Participants with high neuroticism: heart rate variability

Fig. 6 .

 6 Fig. 6. Male participants: heart rate variability

ACKNOWLEDGMENT

This research has been financed by the French Ministère de l'Enseignement supérieur, de la Recherche et de l'Innovation, through the INTERFACES Doctoral School. We would equally like to thank all the participants that took part in our experiments, as well as to Denis Dulgheriu for his help with the annotation process.


Monique Combescure

CIRCULANT MATRICES, GAUSS SUMS AND MUTUALLY UNBIASED BASES, I. THE PRIME NUMBER CASE

In this paper, we consider the problem of Mutually Unbiased Bases in prime dimension d. It is known to provide exactly d + 1 mutually unbiased bases. We revisit this problem using a class of circulant d × d matrices. The constructive proof of a set of d + 1 mutually unbiased bases follows, together with a set of properties of Gauss sums, and of bi-unimodular sequences.

INTRODUCTION

Mutually Unbiased Bases (MUB's) are a set {B 0 , ..., B N } of orthonormal bases of C d such that the scalar product in C d of any vector in B j with any vector in B k , ∀j = k is of modulus d -1/2 . Starting from the natural base B 0 consiting of vectors v 1 = (1, 0, ...0), v 2 = (0, 1, 0, ..., 0), ..., v d = (0, 0, ..., 1), it is known that this problem reduces to find N unitary Hadamard matrices P j such that P * j P k is also a unitary Hadamard matrix ∀j = k. (A unitary matrix is Hadamard if all its entries are of modulus d -1/2 ). The problem has been solved in prime power dimension d = p n , p, n ∈ N, p prime, and yields exactly d + 1 MUB's which is the maximum number of MUB's ( [START_REF] Bandyopadhyay | A new proof of the existence of mutually unbiased bases[END_REF] and references herein contained). If d is factorizable in p m 1 1 p m 2 2 ... with p i = p j prime numbers, it is known that one has at least N = min p m i i [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF].

In this paper we show that in prime dimension d = p, the Discrete Fourier Transform F together with a suitable circulant matrix C allow to construct a set of d+1 MUB's. In addition this construction allows to obtain, as a by-product, a set of properties 1 of Gauss sums of the following form : (1.1) (F d is the field of residues modulo d). A direct proof of this property is given in [START_REF] Saffari | Quadratic Gauss Sums[END_REF]. Similar results on generalized Gauss Sums appear in [START_REF] Albouy | SU 2 nonstandard bases : the case of mutually unbiased bases[END_REF]. The definition of F and of circulant matrices is given below. The natural role played by circulant matrices in this context is a new result. The circulant unitary matrices are known to be in one-to-one correspondence with the bi-unimodular sequences c = (c 1 , c 2 , ..., c d ) [START_REF] Björck | New classes of finite unimodular sequences with unimodular Fourier transforms. Circulant Hadamard matrices with complex entries[END_REF], namely sequences such that

|c j | = |(F c) j | = 1
, where F is the discrete Fourier transform. Not surprisingly Gauss sums appear naturally in this context, since suitable Gauss sequences are examples of bi-unimodular sequences. At the end of this paper, we consider the case of non-prime dimension, and show that Gauss sums properties can be deduced in the odd and in the even dimension cases. In a forthcoming work we shall consider the case of prime power dimensions and show that the theory of block-circulant matrices with circulant blocks solve the MUB problem in that case.

A d × d matrix is Hadamard if all its entries have equal moduli [START_REF] Hadamard | Résolution d'une question relative aux déterminants[END_REF], and

H * H = d 1l Definition 1.1 A d × d matrix H is Hadamard if |H j,k | is constant ∀j, k = 1, ..., d, and
H * H = d 1l.
We call H a "unitary Hadamard matrix" if

|H j,k | = d -1/2 , ∀j, k = 1, ..., d, and d l=1 H * j,l H l,k = δ j,k Definition 1.2 A d×d matrix C is called circulant [6]
, and denoted circ(c 0 , c 1 , ..., c d-1 ), if all its rows and columns are successive circular permutations of the first. It is of the form

C =     c 0 c d-1 . . c 1 c 1 c 0 . . c 2 . . . . . c d-1 c d-2 . . c 0     Proposition 1.3 (i) The set C of all d × d circulant matrices is a commutative algebra. (ii) C is a subset of normal matrices (ii) Let V = circ(0, 0, ..., 1). Clearly V d = 1l.
Then C is circular if and only if it commutes with V , and one has for any sequence c = (c 1 , ..., c d ) ∈ C d , C = circ(c 1 , ..., c d ) :

C = P c (V ) = c 0 1l + c d-1 V + ... + c 1 V d-1
where P c is the polynomial

P c (x) = d k=0 c k x -k
Proof : See [START_REF] Davis | Circulant matrices[END_REF] For the product of two circulant matrices C, C ′ (that therefore commute with V ), one has

V CC ′ = CV C ′ = CC ′ V which establishes that CC ′ is indeed circulant.
Moreover it is well-known that there is a close link between the circulant matrices and the discrete Fourier transform. Namely the latter diagonalizes all the circulant matrices. The Discrete Fourier Transform is defined by the following d × d unitary matrix F with matrix elements :

F j,k = d -1/2 exp 2iπjk d , j, k = 0, 1, ..., d -1 (1.2) Proposition 1.4 (i)
The circulant matrix V = circ(0, 0, ..., 1) is such that

F * V F = U ≡ diag(1, ω, ω 2 , ..., ω d-1 )
where

ω = exp 2iπ d (1.3) (ii) Let C = circ(c 0 , c 1 , ..., c d-1 ) be a circulant d × d matrix.
Then

F * CF = √ d diag(ĉ 0 , ĉ-1 , ..., c -(d-1) )
where

ĉl = 1 √ d d-1 k=0 c k ω kl (1.4) Proof : (i) It is enough to check that v k , the k-th column vector of F which has components (v k ) j = ω jk √ d , j, k = 0, 1, ..., d -1 is eigenvector of V with eigenvalue ω k , which is immediate since (V v k ) j = ω k(j+1) √ d = ω k (v k ) j (ii) One has (Proposition 1.3(ii)) C = d-1 k=0 c k V -k Thus F * CF = d-1 k=0 c k (F * V F ) -k = d-1 k=0 c k U -k = diag(d 0 , ..., d d-1 )
with

d l = d-1 k=0 c k ω -lk = √ d ĉ-l Lemma
d-1 k=0 ck c [j+k] = d-1 l=0 |ĉ l | 2 ω -jl
where the Fourier transform ĉ of c has been defined in (1.4).

Proof : For any j = 0, ..., d -1, one has

d-1 l=0 |ĉ l | 2 ω -jl = 1 d d-1 l=0 ω -jl d-1 k=0 ck ω -lk d-1 k ′ =0 c k ′ ω k ′ l = d-1 k,k ′ =0 ck c k ′ 1 d d-1 l=0 ω l(k ′ -k-j) = d-1 k=0 c [j+k] ck since d -1 d-1 l=0 ω l(k ′ -j-k) = δ k ′ ,[j+k]
It is known ( [START_REF] Björck | New classes of finite unimodular sequences with unimodular Fourier transforms. Circulant Hadamard matrices with complex entries[END_REF], [START_REF] Turyn | Sequences with small correlation[END_REF]) that circulant unitary Hadamard matrices are in one-toone correspondance with bi-unimodular sequences c = (c 0 , c 1 , ..., c d-1 ). d, where ĉj is defined by (1.4).

Definition 1.6 A sequence c = (c 0 , c 1 , ..., c d-1 ) is called bi-unimodular if one has |c j | = |ĉ j | = 1, ∀j = 1, ...,
Proposition 1.7 Let (c 0 , ..., c d-1 ) be a bi-unimodular sequence. Then the circulant matrix

C = d -1/2 circ(c 0 , c 1 , ..., c d-1
) is an unitary Hadamard matrix.

Proof : This is a standard "if and only if" statement. One uses Lemma 1.5 :

d-1 k=0 ck c [j+k] = d-1 l=0 |ĉ l | 2 ω -jl
But since |ĉ l | = 1, ∀l = 0, ..., d -1, the RHS is simply dδ j,0 , and therefore

d-1 k=0 ck c [k+j] = d δ j,0
which proves the unitarity of the circulant Hadamard matrix C.

In all that follows we call indifferently F or P 0 the discrete Fourier transform.

In [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF], the authors introduce for any dimension d being the power of a prime number a set of operators called "rotation operators" which can be viewed as "circulant matrices" (this property is however not put forward explicitely by the authors). In this paper, restricting ourselves to the prime number case, we show that these operators can be used to define a set of d+1 Mutually Unbiased Bases in dimension d.

Mutually Unbiased bases are extensively studied in the framework of Quantum Information Theory. They are defined as follows :

Definition 1.8 A set {B 1 , B 2 , ..., B m } of orthonormal bases of C d is called MUB if for any vector b (k) j ∈ B k and any b (k ′ ) j ′ ∈ B k ′ one has |b (k) j • b (k ′ ) j ′ | = d -1/2 , ∀k = k ′ = 1, ..., m, ∀j, j ′ = 1, ..., d
where the dot represents the Hermitian scalar product in C d . Remark 1.9 It is trivial to show that if the orthonormal bases B k are the column vectors of an unitary matrix A k , then the property that must satisfy the A k 's in order that {1l, B 1 , ..., B m } are MUB's is that all A k , k = 1, ..., m and A * k A k ′ , k = k ′ = 1, ..., m are unitary Hadamard matrices. Namely if u j , v k are column vectors for unitary matrices A, A ′ respectively, then

u j • v k = (A * A ′ ) j,k
Thus unitary Hadamard matrices play a major role in the MUB problem.

It is known that the maximum number of MUB's in any dimension d is d + 1, and that this number is attained if d = p m , p being a prime number. In this paper, restricting ourselves to m = 1, we revisit the proof of this property, using circulant matrices introduced by [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF]. We then show that it implies beautiful properties of Gauss sums, namely the following ( [START_REF] Saffari | Quadratic Gauss Sums[END_REF]) : This property will appear as a subproduct of our study of MUB's for d a prime number ≥ 3 via the circulant matrices method. As stressed above, the link between circulant matrices and bi-unimodular sequences is well established. What is new here is the fact that the MUB problem via a circulant matrix method allows to recover the bi-unimodularity of Gauss sequences. The crucial role played by the Gauss sequence is due to the crucial role played by the Discrete Fourier Transform (or in other therms the Fourier-Vandermonde matrices) in the MUB problem for prime numbers. Let us introduce it now explicitely.

It is known since Schwinger ( [START_REF] Schwinger | Unitary Operator Bases[END_REF]) that a simple toolbox of unitary d × d matrices sometimes refered to as "generalized Pauli matrices" U, V allows to find MUB's. U, V generate the discrete Weyl-Heisenberg group [START_REF] Weyl | Gruppentheorie and Quantenmechanik[END_REF]. Denote by ω the primitive root of unity (1.3). The matrix U is simply

U = diag(1, ω, ω 2 , ..., ω d-1 )
which generalizes the Pauli matrix σ z to dimensions higher than two. The matrix V generalizes σ x :

V = circ(0, 0, ..., 1) =       0 1 0 . . 0 0 0 1 . . 0 . . . . . . 0 0 0 . . 1 1 0 0 . . 0      
Then one has the following result : Theorem 1.11 (i) The U, V matrices obey the ω-commutation rule :

V U = ωUV (ii)
The Discrete Fourier Transform matrix P 0 = F defined by (1.2), namely

P 0 = 1 √ d       1 1 1 . . 1 1 ω ω 2 . . ω d-1 1 ω 2 ω 4 . . ω 2(d-1) . . . . . . 1 ω d-1 ω 2(d-1) . . ω (d-1)(d-1)       diagonalizes V , namely V = P 0 UP * 0 = P * 0 U * P 0 (iii) One has P 4 0 = 1l
(ii) is simply Proposition 1.4(i). For the proof of (iii) reminiscent to the properties of continuous Fourier transform, it is enough to check that In [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF] we have shown that for d odd one can add to the general toolbox of unitary Schwinger matrices V a diagonal matrix D of the form

P 2 0 = W =         1
D = diag(1, ω, ω 3 , ..., ω k(k+1)/2 , ..., 1)
so that the MUB problem for odd prime dimension reduces to properties of U, V, D, and that certain properties of quadratic Gauss sums follow as a by-product.

THE d=CASE

We have U = σ z and V = σ x , σ z , σ x being the usual Pauli matrices. Since UV = σ y , finding MUB's in dimension d = 2 amounts to diagonalize σ x , σ y . One has :

σ x = P 0 σ z P * 0 σ y = P 1 σ z P * 1 with P 0 = 1 √ 2 1 1 1 -1 , P 1 = 1 √ 2
1 i i 1 P 1 is circulant.
Proposition 2.1 The set {1l, P 0 , P 1 } defines three MUB's in dimension 2.

Since the matrices P 0 , P 1 are trivially unitary Hadamard matrices, it is enough to check that P * 0 P 1 is itself a unitary Hadamard matrix, which holds true since

P * 0 P 1 = e iπ/4 √ 2 1 1 -i -i 3 THE PRIME DIMENSION d ≥ 3
d being prime, we denote by F d the Galois field of integers mod d.

Let us recall the definition of the "rotation operator" of [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF], which, as already stressed in nothing but a circulant matrix in the odd prime dimension d.

Definition 3.1 Define R as an unitary operator commuting with V and diagonalizing V U.

Proposition 3.2 (i) R is a circulant matrix. (ii) R k is also circulant ∀k ∈ Z.
This follows from Proposition 1.3.

Therefore we are led to consider a subclass of circulant matrices that are unitary. They must satisfy : ∀k = 0, ..., d -

1 |c k | = d -1/2 and ∀k = 1, ..., d -1 d-1 j=0 cj c [d-k+j] = 0 (orthogonality condition).
Now it remains to show that such a matrix R exists. In [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF] we have constructed a unitary matrix P 1 that diagonalizes V U. It is defined as

P 1 = D -1 P 0
for any d odd integer (not necessarily prime). We have established the following result : Proposition 3.3 (i) For any odd integer d, the matrix P * 0 P 1 is a unitary Hadamard matrix.

(ii) For d ≥ 3 odd integer, let P k := D -k P 0 . Then P * 0 P k is a unitary Hadamard matrix for all k coprime with d. (iii) The matrix D defined above is such that

|TrD k | = √ d, ∀k ∈ F d coprime with d
For the simple proof of this result see [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF]. (iii) is a simple consequence of (i) and(ii). Namely the eigenvector of V U belonging to the eigenvalue 1 has components

v j = d -1/2 ω -j(j+1)

2

Since P * 0 P 1 is unitary Hadamard matrix, the element of P * 0 P 1 of the first row and first column is simply and since its modulus must be d -1/2 we obtain (iii) for k = 1. The proof for any k coprime with d can be obtained similarly using (ii).

d -1 d-1 j=0 ω -j(j+1)
The "problem" is that P 1 is not circulant. However the circulant matrix R is obtained from P 1 by multiplying the kth column vector of P 1 by a phase which is

ω -k(k-1)

2

This operation preserves the fact that it is unitary and that it diagonalizes V U. We thus have :

V U = P 1 UP * 1 = RUR * (3.6)
Proposition 3.4 Let R be the matrix :

R = d -1/2 circ (1, ω -1 , ω -3 , ..., ω -k(k+1)/2 , ..., 1)
It is a unitary Hadamard matrix.

Proof : By construction it is a unitary Hadamard matrix, since P 1 is. To prove the fact that it is circulant, it is enough to know that

(P 1 ) j,k = d -1/2 ω jk-j(j+1) 2 thus R jk = d -1/2 ω jk-j(j+1) 2 - k(k-1) 2 = d -1/2 ω -(j-k)(j- k+1) 2 (3.7)
since

jk - j(j + 1) 2 - k(k -1) 2 = - (j -k)(j -k + 1)
2 Thus all column vectors are obtained from the first by the circularity property.

Furthermore the R k have the property that they diagonalize V k U, ∀k = 1, ..., d -1:

Theorem 3.5 (i) R = αP 0 DP * 0 where α := d -1/2 d-1 k=0 ω -k(k+1)/2 is a complex number of modulus 1. (ii) R d = α d 1l where 1l denotes the unity d × d matrix. (iii) R k U(R * ) k = V k U, ∀k = 0, ..., d
The proof is extremely simple :

(i) We have shown that c j = ω -j(j+1) 2
is a bi-unimodular sequence, thus α is a complex number of modulus one. Moreover from Proposition 1.4 (ii), the unitary matrix are bi-unimodular.

R = d -1/2 circ(c j ) is such that R = P * 0 RP 0 = diag(ĉ -k ) Proposition 3.8 (i)
exp iπ k dj 2 + (k + 2m)j = √ k Proof : Since R k = α k P 0 D k P * 0 , the matrix elements of R k are (R k ) m,l = α k d d-1 j=0 ω j(m-l)+k j(j+1) 2 Since R k is circulant,
Remark 3.10 This property is known, but has an extension in the non prime odd dimensions. See next section.

It is known that the diagonalization of V U k , k = 0, ..., d-1 provides a set of d+1 MUB's for a prime p. Here we show that the same is true with the diagonalization of V k U, k = 0, ..., d -1.

Theorem 3.11 Let d ≥ 2 be a prime dimension. Then the orthonormal bases defined by the unitary matrices 1l, P 0 , R, R 2 , ..., R d-1 provide a set of d + 1 MUB's.

Proof : For d = 2 this has been already proven in Section 2. For d ≥ 3 (thus odd, since it is prime), it is enough to check that : (i) P 0 , R k , k = 1, ..., d -1 are unitary Hadamard matrices, together with (ii)

P * 0 R k , k = 1, ..., d -1 and (R k ′ ) * R k , 1 ≤ k ′ < k ≤ d -1. Since (i) has been already established, it remains to show (ii). Since R k = α k P 0 D k P * 0 we have P * 0 R k = α k D k P * 0
which is trivially an unitary Hadamard matrix (since P 0 is, α is of modulus 1 and D is diagonal and unitary).

For (R * ) k ′ R k it is trivial since (R * ) k ′ R k = R k-k ′ which is unitary Hadamard for any k = k ′ , k, k ′ = 1, ..., d -1.

THE CASE OF ARBITRARY ODD DIMEN-SION

We have shown in [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF] that for any odd dimension d ≥ 3 the matrices P * 0 P k is an unitary Hadamard matrix provided k is co-prime with d. This can be transfered to a similar property for the matrix R -k , and therefore to the bi-unimodularity of the sequence g (k) defined in (1.5).

THE CASE OF ARBITRARY EVEN DIMEN-SION

Let d be even and ω = exp 2iπ d

We denote ω 1/2 = e iπ/d . One defines the Discrete Fourier Transform F as usually.

The theory of circulant matrices is also pertinent for even dimensions d ≥ 4. Namely in that case the matrix D ′ = diag(1, ω -1/2 , ..., ω -k 2 /2 , ..., ω -1/2 ) has been shown ( [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF]) to be such that the unitary Hadamard matrix

P 1 = D ′ F diagonalizes V U.
But the circulant matrix R obtained by multiplying the k-th column vector of P 1 by ω -k 2 /2 also diagonalizes V U :

Proposition 5.1 The circulant matrix whose matrix elements are

R j,k = 1 √ d ω -(j-k) 2 /2
diagonalizes V U and is such that F * R is an unitary Hadamard matrix. Remark 5.3 R 2 is circulant, unitary, but not Hadamard. Thus it does not help to find more than 3 MUB's in even dimensions. In dimensions d = 2 n , another method is necessary to prove that there exists d + 1 MUB's.

  ∈ F d , l ∈ F d coprime with d, d ≥ 3

1 . 5

 15 For any k ∈ N, we denote by [k] the rest of the division of k by d. Given any sequence c = (c 0 , ..., c d-1 ) ∈ C d its autocorrelation function obeys

Proposition 1 . 10 1 ( 1 . 5 )

 110115 Let d ≥ 3 be an odd number. Then ∀k = 1, ..., d -1 coprime with d the sequences g (k) := exp iπkj(j + 1) d j=0,...,dare bi-unimodular. Thus (1.1) holds true.

  Thus W = 1l in dimension d = 2, and W 2 = 1l, ∀d ≥ 3.

2

 2

2 +Corollary 3 . 9

 239 it is unitary Hadamard matrix if and only if the matrix elements of the first column (l=0) are of modulus d -1/2 , thus if and only if j(k + 2m)] = √ d which proves (i). (ii) Using the reciprocity theorem for Gauss sums ([3]), we have for all integers a, b with ac = 0 and ac + d even that the quantity S(a, b, d) := ad) -b 2 /ad] S(-d, -b, a) Thus |S(a, b, d)| = √ d if and only if |S(-d, -b, a)| = √ a. Applying if to a = k = 1, ..., d -1 coprime with d and b = 2m + k, and taking the complex conjugate yields the result. Namely ad + b = dk + k + 2m is even for all k = 0, ..., d -1 since d is odd. Let d ≥ 3 be a prime number. Then for any k = 1, 2, ..., d -1 the sequences g (k) := ω k j(j+1) 2 j=0,...,d-1

Proposition 4 . 1

 41 Let d ≥ 3 be an odd integer, and k be any number coprime with d. Then (i) R k is an unitary Hadamard matrix. (ii) The sequence g (k) is bi-unimodular. (iii) Both properies are equivalent. This implies Proposition 1.10.

Theorem 4 . 2

 42 Let d be odd and k > 2 be the smallest divisor of d. Then the orthonormal bases defined by the unitary matrices 1l, F, R, R 2 , ..., R k-1 provide a set of k + 1 MUB's in dimension d.

2 R

 2 j,k only depends on j-k thus is circulant (and unitary). Therefore it is diagonalized by F , namely there exists an unitary diagonal matrix D ′′ such thatF * RF = D ′′Again this implies that F * R is an unitary Hadamard matrix. ⊓ ⊔ Corollary 5.2 (i) The orthonormal bases defined by the unitary matrices {1l, F, R} provide a set of 3 MUB's in arbitrary even dimension d. (ii) One has the following property of quadratic Gauss sums for d even :

  Let d be an odd prime. Then for any k = 1, 2, ..., d -1 R k is an unitary Hadamard matrix if and only if one has

	d-1 j=0	exp	iπ d	[kj 2 + j(k + 2m)] =	√	d, ∀m = -d + 1, ..., d -1
	(ii) Under the same conditions R k is a unitary Hadamard matrix if and only if
				k-1
				j=0

Acknowledgments : It is a pleasure to thank B. Helffer for his interest in this work, and to Bahman Saffari for interesting discussions and for providing to me reference [12].

But

(iii) is obtained by recurrence. Namely it is true for k = 1 by (3.6). For k ≥ 2 one has :

There is a direct link between the matrices P k that diagonalize V U k and the R k that diagonalize V k U :

Theorem 3.6 α being the complex number of modulus one defined above, we have for any k = 0, ..., d -1

Proof : In [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF] we have proven that P k = D -k P 0 diagonalizes V U k . But one has Proof : R k is circulant and unitary since R is. Therefore we have only to check that it is Hadamard. We have :

But we recall that P 2 0 equals the permutation matrix W . Thus all matrix elements of R k equal, up to a phase, some matrix elements of P * 0 P k . But we have established in [START_REF] Combescure | The Mutually Unbiased Bases Revisited[END_REF] that the matrix P * 0 P k is unitary Hadamard ∀k = 1, ..., d -1, thus all its matrix elements are equal in modulus to d -1/2 . This completes the proof. Now we show how this property of the matrix R reflects itself in Gauss sums properties.


Monique Combescure

BLOCK-CIRCULANT MATRICES WITH CIRCULANT BLOCKS, WEIL SUMS AND MUTUALLY UNBIASED BASES, II. THE PRIME POWER CASE

Block circulant matrices with circulant blocks, weil sums and mutually unbiased bases, II. The prime power case M.

INTRODUCTION

The Mutually Unbiased Bases in dimension d are a set {B 1 , ..., B N } of orthonormal bases in C d such that for any b

(k) j ∈ B k , b (k ′ ) j ′ ∈ B k ′ one has b (k) j • b (k ′ ) j ′ = 1 √ d , ∀j, j ′ = 1, ..., d, ∀k ′ = k = 1, ..., N
where b • b ′ = d j=1 b * j b ′ j is the usual scalar product in C d . This notion of mutually unbiased bases emerged in the seminal work of Schwinger 1 [START_REF] Schwinger | Unitary Operator Bases[END_REF] and turned out to be a cornerstone in the theory of quantum information. Furthemore it is strongly linked with the theory of Hadamard matrices [START_REF] Hadamard | Résolution d'une question relative aux déterminants[END_REF] and to the Gauss Sums properties.

An important problem is the maximum number of mutually unbiased bases (MUB) in dimension d. The problem has been completely solved for d = p n where p is a prime number, and n any integer, in which case one can find N = d + 1 MUB's [START_REF] Bandyopadhyay | A new proof of the existence of mutually unbiased bases[END_REF][16] [START_REF] Wootters | Optimal State-Determination by Mutually Unbiased Measurements[END_REF] [10] [START_REF] Chaturvedi | Aspects of mutually unbiased bases in odd-prime-power dimensions[END_REF].

In a previous paper [START_REF] Combescure | Circulant matrices, Gauss sums and the Mutually Unbiased Bases[END_REF] (hereafter refered to as I) we have provided a construction of d + 1 MUB's for d a prime number using a new method involving circulant matrices. Then the MUB problem reduces to exhibit a circulant matrix C which is a unitary Hadamard matrix, such that its powers are also circulant unitary Hadamard matrices. Then using the Discrete Fourier Transform F d which diagonalizes all circulant matrices, we have shown that a MUB in that case is just provided by the set of column vectors of the set of matrices F d , 1l, C, C 2 , ..., C d-1 . Properties of quadratic Gauss sums follow as a by-product of the method.

The present paper is a continuation of I, where we consider d = p n . Here circulant matrices are replaced by a set of block-circulant with circulant blocks matrices. Again the discrete Fourier transform which in this case will be simply F ≡ F p ⊗ F p ⊗ ... ⊗ F p will play a central role since it diagonalizes all block-circulant with circulant blocks matrices. We follow an idea of [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF] to define them. The new result developed here is that these block-circulant matrices with circulant blocks together with F will solve the MUB problem in that case.

Let B k = b (k) 0 , b (k) 1 , ..., b (k) d-1
be orthonormal bases. Then in any given base, they are represented by unitary matrices B k . Taking B 0 to be the natural base, we have that b

(k) j • b (k ′ ) j ′ = (B * k B k ′ ) j,j ′
Thus in order that the bases B k be unbiased, we just need that all the unitary matrices B * k B k ′ , k = k ′ have matrix elements of modulus d -1/2 . Such matrices are known as unitary Hadamard Matrices ([9]).

THE SQUARE OF A PRIME

Let p be a prime number. One defines a primitive p-th root of unity :

ω = exp 2πi p
The Discrete Fourier Transform in C p is Thus it can be written as :

F p = 1 √ p       1 1 1 . . 1 1 ω ω 2 . . ω p-1 1 ω 2 ω 4 . . ω 2(p-1) . . . . . . 1 ω p-1 ω 2(p-1) . . ω (p-1)(p-1)       Definition 2.
C =     a 0 a 1 a 2 . . a d-1 a d-1 a 0 a 1 . . a d-2 . . . . . . a 1 a 2 a 3 . . a 0    
(iii) A diagonal and circulant matrix must be a multiple of the identity matrix 1l. (iv) A d 2 × d 2 matrix is said to be block-circulant if it is of the form

C = circ(C 0 , C 1 , ..., C d-1 )
where the C j are d × d matrices. (v) It is block-circulant with circulant blocks if furthermore the C j are circulant. (vi) A d × d matrix H is a unitary Hadamard matrix if

|H j,k | = d -1/2 , and d-1 k=0 H * j,k H k,l = δ j,l
We define the following p × p unitary matrices X = circ(0, 0, ..., 1)

Z = diag(1, ω, ..., ω p-1 )
They obey the ω-commutation rule :

Lemma 2.2 (i) X p = Z p = 1l (ii) ZX = ωXZ (iii) Furthemore one has F p XF * p = Z
(i) and (ii) are obvious. For a proof of (iii) see [START_REF] Davis | Circulant matrices[END_REF].

Proposition 2.3 Let C = circ(a 0 , ..., a p-1 ).

(i) One has

C = p-1 k=0 a k X p-k
(ii)The discrete Fourier transform diagonalizes the circulant matrices :

F p CF * p = diag(ã 0 , ..., ãp-1 ) where ãj = p-1 k=0 a k ω -jk (iii)
The set of circulant p × p matrices is a commutative algebra.

Proof :

F p CF * p = p-1 k=0 a k Z p-k But Z -k = diag(1, ω -k , ..., ω -k(p-1) ), hence (ii) follows. (iii) is a consequence of (i). Corollary 2.4 If the sequence {a k } k∈F d is such that |a k | = d -1/2 and |ã k | = 1
then C is a circulant unitary Hadamard matrix.

Proof : C is unitarily equivalent to an unitary matrix if

|ã k | = 1. Furthemore |a k | = d -1/2 ,
hence the result follows (see [START_REF] Combescure | Circulant matrices, Gauss sums and the Mutually Unbiased Bases[END_REF]).

The discrete Fourier transform in C p 2 is defined as follows

F = F p ⊗ F p (2.1)
It has the following important property (similar to the property that the discrete Fourier transform diagonalizes all circulant matrices) : Proposition 2.5 (i) F is an unitary Hadamard matrix. (ii) All block-circulant matrices C with circulant blocks are diagonalized by F :

F CF * = D where D is a p 2 × p 2 diagonal matrix.
For a proof of this result see [START_REF] Davis | Circulant matrices[END_REF].

We shall be interested in finding block-circulant with circulant blocks unitary matrices in C p 2 that are Hadamard matrices. An example is of course C ⊗ C ′ where C, C ′ are unitary circulant Hadamard matrices.

For p a prime number, denote by F p the field of residues modulo p. The corresponding Galois field GF (p 2 ) is defined as follows. For any p there exists an irreducible polynomial of degree two, with coefficients in F p so that if we denote by α a root of this polynomial,

GF (p 2 ) = {mα + n} m,n∈Fp
The product θ

• θ ′ ∈ GF (p 2 ) for θ, θ ′ ∈ GF (p 2
) is obtained using the irreducible polynomial which expresses α 2 in terms of α and 1.

The additive characters χ(θ) in GF (p 2 ) are defined as follows:

Definition 2.6 The additive characters on GF (p 2 ) are :

χ(θ) = exp 2iπ p trθ where trθ = θ + θ p Lemma 2.7 They satisfy : (i) χ(θ + θ ′ ) = χ(θ)χ(θ ′ ) (ii) One has : θ∈GF (p 2 ) χ(θ) = 0 (iii) θ ′ ∈GF (p 2 ) χ(θ • θ ′ ) = p 2 δ θ,0 (2.2)
We take as natural basis in C p 2 the set of states labelled by θ ∈ GF (p 2 ), in the following order :

B ≡ {|0 , |α , |2α , ..., |1 , |1 + α , ..., |p -1 , ..., |p -1 + (p -1)α }
Labelled by θ ∈ GF (p 2 ) we define a set of unitary operators in C p 2 such that :

Definition 2.8 (i) The set of operators F ≡ {X θ } θ∈GF (p 2 ) obeys X θ |θ ′ = |θ + θ ′ , ∀θ ′ ∈ GF (p 2 ) (2.3) (ii) The set of diagonal operators F ′ ≡ {Z θ } θ∈GF (p 2 ) obeys Z θ |θ ′ = χ(θ • θ ′ )|θ , ∀θ ′ ∈ GF (p 2 ) (2.4)
They obey :

Proposition 2.9 (i) Z θ X θ ′ = χ(θ • θ ′ )X θ ′ Z θ (2.5) (ii)
The operators in F , F ′ obey the group commutative property :

X θ+θ ′ = X θ X θ ′ = X θ ′ X θ , Z θ+θ ′ = Z θ Z θ ′ = Z θ ′ Z θ (2.6) (iii) Z 0 = X 0 = 1l
Proof : Take any ϕ ∈ GF (p 2 ). Then

Z θ X θ ′ |ϕ = χ(θ • (θ ′ + ϕ))|θ ′ + ϕ = χ(θ • θ ′ )X θ ′ Z θ |ϕ = χ(θ • θ ′ )χ(θ • ϕ)|θ ′ + ϕ
We also have (ii) :

Z θ+θ ′ |ϕ = χ((θ + θ ′ ) • ϕ)|ϕ = χ(θ • ϕ)χ(θ ′ • ϕ)|ϕ = Z θ Z θ ′ |ϕ ⊓ ⊔ Theorem 2.10 (i) F = {X m ⊗ X n } m,n∈Fp
More precisely one has

X mα+n = X n ⊗ X m (2.7)
(ii) All operators in F are represented by unitary block-circulant with circulant blocks p 2 × p 2 matrices.

(iii)

F ′ = {Z m ⊗ Z n } m,n∈Fp
(iv) All operators in F ′ are represented by diagonal p 2 × p 2 matrices. (v) For any θ ′ ∈ GF (p 2 ) there exists a θ ∈ GF (p 2 ) such that

F X θ ′ F * = Z θ (2.8)
Proof of (i) : It is enough to see that X α = 1l ⊗ X and X 1 = X ⊗ 1l since the other matrices X mα+n will be given by the chain rule :

X mα+n = X m α X n 1
But these are obviously block-circulant with circulant blocks matrices. One has for θ ′ = mα + n :

F X mα+n F * = F X m α X n 1 F * = (F p ⊗ F p )(X n ⊗ X m )(F * p ⊗ F * p ) = Z n ⊗ Z m which is Z θ for some θ ∈ GF (p 2
F CF * = θ ′ ∈GF (p 2 ) λ θ ′ F X θ ′ F * = θ ′ ∈GF (p 2 ) λ θ ′ Z f (θ ′ )
which is a diagonal matrix.

To find the MUB's in dimension p 2 it is enough to exhibit a partition of the set of unitary operators :

E ≡ {Z θ X θ ′ } θ,θ ′ ∈GF (p 2 )
into a set of commutant families : We define

F 0 = F \ {1l}
One wants :

E = F 0 θ∈GF (p 2 ) C θ ∪ {1l}
The family C θ will be defined as follows :

Definition 2.12 Let for any θ ∈ GF (p 2 )

E θ = {Z θ ′ X θ•θ ′ } θ ′ ∈GF (p 2 ) Define C θ = E θ \ {1l} Proposition 2.13 (i) E 0 = F ′ (ii) E θ is a commuting family ∀θ ∈ GF (p 2 ). (iii) E = F 0 θ∈GF (p 2 ) C θ ∪ {1l} is a partition of E. Proof : (i) is obvious. (ii) ∀θ ′ , θ ′′ ∈ GF (p 2 ) one has Z θ ′ X θ•θ ′ Z θ ′′ X θ ′′ •θ = χ(-θ • θ ′ • θ ′′ )Z θ ′ +θ ′′ X θ•(θ ′ +θ ′′ ) = Z θ ′′ X θ•θ ′′ Z θ ′ X θ•θ ′′ (iii) C θ and F 0 contain p -1 elements. The classes C θ for different θ are disjoint. Therefore θ∈GF (p 2 )
C θ contains p(p -1) elements. One has :

p -1 + p(p -1) + 1 = p 2
which is the total number of elements in E.

Since all the unitary operators in C θ commute, they can be diagonalized by the same operator R θ . In the above cited work [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF] they are defined as "rotation operators". In fact we shall see that they are represented in the basis B by block-circulant with circulant block matrices. The first main result of this paper is the following : Theorem 2.14 (i) There exists a set {R θ } θ∈GF (p 2 ) of unitary operators which diagonalize all the operators of the class C θ , ∀θ ∈ GF (p 2 ). (ii) The operators R θ for θ = 0 are represented in the basis B by block-circulant with circulant block matrices which are unitary Hadamard matrices. (iii) For p ≥ 3 they obey the group law :

R θ+θ ′ = R θ R θ ′ , ∀θ, θ ′ ∈ GF (p 2 ) Proof : It is enough to show that for any θ ∈ GF (p 2 )\ {0} the R θ can be expanded as R θ = θ ′ ∈GF (p 2 ) λ (θ) θ ′ X θ ′ (2.9)
since they will automatically represented in the basis B by block-circulant with circulant blocks matrices. One has to check that

R -1 θ Z θ ′ X θ•θ ′ R θ = µ θ,θ ′ Z θ ′ , ∀θ ′ ∈ GF (p 2 )
Since the operators Z θ ′ X θ•θ ′ are unitary, the µ θ,θ ′ are necessarily complex numbers of modulus one. But

Z θ ′ X θ•θ ′ θ ′′ λ (θ) θ ′′ X θ ′′ = Z θ ′ θ ′′ λ (θ) θ ′′ X θ ′′ +θ•θ ′ = µ θ,θ ′ θ ′′′ λ (θ) θ ′′′ X θ ′′′ Z θ ′ = µ θ,θ ′ Z θ ′ θ ′′′ χ(-θ ′ •θ ′′′ )λ (θ) θ ′′′ X θ ′′′
Equating the coefficients of X θ ′′′ in both sides we get

λ (θ) θ ′′′ -θ•θ ′ = µ θ,θ ′ χ(-θ ′ • θ ′′′ )λ (θ) θ ′′′
Taking θ ′′′ = 0 and assuming that λ

(θ) 0 = p -1 , ∀θ ∈ GF (p 2 ) we get λ (θ) -θ•θ ′ = p -1 µ θ,θ ′ or equivalently, since θ = 0 λ (θ) θ ′ = p -1 µ θ,-θ -1 •θ ′ This proves that all the λ (θ) θ ′ must be of modulus p -1 .
Therefore since all the X θ are represented by unitary matrices that have non-zero elements (actually 1) where all the others have zeros, and since every matrix element of R θ is of the form λ (θ) θ ′ for some θ ′ ∈ GF (p 2 ), this proves that all the R θ are represented by Hadamard matrices. Now we have to check the compatibility condition. We reexpress it in terms of µ θ,θ ′ . Supressing the index θ in the µ θ,θ ′ for simplicity, we need to have ∀θ ′ , θ ′′ ∈ GF (p 2 )

µ -θ -1 (θ ′′ -θθ ′ ) = µ θ ′ µ -θ -1 θ ′′ χ(-θ ′ • θ ′′ ) or in other terms µ θ ′ +θ ′′ = µ θ ′ µ θ ′′ χ(θ • θ ′ • θ ′′ ) (2.10)
But this results easily from the group property of the X θ 's and Z θ 's (2.3, 2.4) : [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF] it is shown that for p ≥ 3 the solution of (2.10) with µ θ,0 = 1 is

R -1 θ Z θ ′ +θ ′′ X θ•(θ ′ +θ ′′ ) R θ = χ(θθ ′ θ ′′ )R -1 θ Z θ ′ X θθ ′ R θ R -1 θ Z θ ′′ X θθ ′′ R θ = χ(θθ ′ θ ′′ )µ θ,θ ′ µ θ,θ ′′ Z θ ′ +θ ′′ In
µ θ,θ ′ = χ(2 -1 θ • θ ′2 ) (2.11)
Thus we deduce that λ (θ)

θ ′ = p -1 χ(2 -1 θ -1 • (θ ′ ) 2 ) (2.12)
We now prove the unitarity of R θ . For θ = 0 this is obvious since R 0 = 1l. It is enough to check that for θ = 0 one has :

θ ′ ∈GF (p 2 ) (λ (θ) θ ′ ) * λ (θ) θ ′ +θ ′′ = δ θ ′′ ,0
One has :

θ ′ ∈GF (p 2 ) (λ (θ) θ ′ ) * λ (θ) θ ′ +θ ′′ = 1 p 2 θ ′ ∈GF (p 2 ) µ * θ,-θ -1 •θ ′ µ θ,-θ -1 •(θ ′ +θ ′′ ) = 1 p 2 θ ′ ∈GF (p 2 ) |µ θ,-θ -1 •θ ′ | 2 µ θ,-θ -1 •θ ′′ χ(θ -1 θ ′ θ ′′ ) = µ θ,-θ -1 •θ ′′ 1 p 2 θ ′ ∈GF (p 2 ) χ(θ -1 θ ′ θ ′′ ) = δ θ ′′ ,0
where we have used (2.10) and (2.2), together with the fact that θ -1 • θ ′′ = 0 implies θ ′′ = 0 due to the field property of GF (p 2 ). Thus one has [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF]. For p = 2 it has to be suitably modified as shown in [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF] (see remark below). Let us see how it works for p ≥ 3 :

R -1 θ = R * θ , ∀θ ∈ GF (p 2 ) (iii) The group law R θ+θ ′ = R θ R θ ′ for p ≥ 3 has been established in
(R * 1 ) n (R * α ) m Z θ ′ X (n+mα)•θ ′ R n 1 R m α = (R * 1 ) n (R * α ) m Z θ ′ X θ ′ •mα R m α X nθ ′ R n 1 = µ(mα, θ ′ )(R * 1 ) n Z θ ′ X nθ ′ R n 1 = µ mα,θ ′ µ n,θ ′ Z θ ′ = µ mα+n,θ ′ Z θ ′ holds for p ≥ 3 since µ mα+n,θ ′ = µ mα,θ ′ µ n,θ ′ , ∀θ ′ ∈ GF (p 2 )
which easily follows from (2.11) for p ≥ 3, and the additivity of the characters. For any θ ∈ GF (p n ) the operators X θ , Z θ , R θ are defined in [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF] and the R θ obey a group law (resp. a modified group law) if p ≥ 3 (resp. p = 2). As previously we have X θ ∈ X k 1 ⊗ X k 2 ⊗ ... ⊗ X kn , with k j ∈ F p and

Z θ ∈ Z k 1 ⊗ Z k 2 ⊗ ... ⊗ Z kn k i ∈Fp and R θ = θ ′ ∈GF (p n ) λ (θ) θ ′ X θ ′ with λ (θ) θ ′ of modulus 1 √ p n . The λ (θ)
θ ′ are given for p ≥ 3 similarly to (2.12) by λ (θ)

θ ′ = p -n/2 χ(2 -1 θ -1 (θ ′ ) 2 ) (3.13)
All the results of the previous section are easily generalized. 4 Weil sums for d = p n , p ≥ 3

The Weil sums in dimension p n are the equivalent of the Gauss sums for d = p (p prime number). The characters χ(θ), θ ∈ GF (p n ) replace the powers ω n , n ∈ F p . Usually in the literature (see for example [START_REF] Wootters | Optimal State-Determination by Mutually Unbiased Measurements[END_REF]), the Weil sums properties are used to solve the MUB problem. Here, as in [START_REF] Combescure | Circulant matrices, Gauss sums and the Mutually Unbiased Bases[END_REF], we do the converse. In the previous sections we have constructed the d + 1 bases, and we shall deduce the Weil sums properties from this construction.

  power n, with coefficients in F p . Thus elements of the Galois field GF (p n ) are of the form i where c i ∈ F p and α is a root of the characteristic polynomial. The characters areχ(θ) = exp 2iπ p tr(θ)where tr(θ) = θ + θ p + ... + θ p n-1

Theorem 3 . 1

 31 The unitary Hadamard matrices F, R θ for θ ∈ GF (p n ) define a set of p n + 1 MUB's in C p n .

Theorem 4 . 1

 41 Let p ≥ 3. Then for any θ ∈ GF (p n )\ {0} and any θ ′ ∈ GF (p n ) we haveθ ′′ ∈GF (p n ) χ(θ • (θ ′′ ) 2 + θ ′ • θ ′′ ) = √ p n (4.14)

1

  Consider a d-periodic sequence a 0 , a 1 , ..., a d-1 , a 0 , a 1 , ....

	(i) A d × d matrix D is diagonal and called diag(a 0 , ..., a d-1 ) if its matrix elements satisfy
	D j,k = a k δ j,k , ∀j, k = 0, 1, ..., d -1 (ii) A d × d matrix C is called circulant and denoted C = circ(a 0 , ..., a d-1 ) if its matrix elements satisfy
	C j,k = a (d-1)j+k

  Proposition 2.11 All block-circulant matrices with circulant blocks commute and are diagonalized by F . Proof : It follows from (2.8) that if C = θ ′ λ θ ′ X θ ′ is a block-circulant matrix with circulant blocks, one has

	One recalls a famous result [8] :	). ⊓ ⊔

Remark 2.15 For p = 2 the group law is not satisfied (see [START_REF] Klimov | Geometrical approach to the discrete Wigner function[END_REF]). One has instead a very similar property (modified group law ) :

The second main result of this paper is the following :

Proof : Each R θ is represented by an unitary Hadamard matrix, and so is F . Due to the group property,

with D θ an unitary diagonal matrix, since F diagonalizes all block-circulant matrices with circulant blocks. The product of D θ with the unitary Hadamard matrix F * is obviously an unitary Hadamard matrix.

In the case of dimension 2 2 one has instead of the group property that

Since X θ ′′ has exactly one non-vanishing element ( 1) on each line and column, the product R θ ′ -θ X θ ′′ is indeed an unitary Hadamard matrix. ⊓ ⊔

THE CASE d = p n

The case d = p n with general power n can be treated similarly. There is a notion of block-circulant matrices with block-circulant blocks and building block p×p matrices which are circulant which generalizes the case n = 2. These are diagonalized by the Discrete Fourier Transform F in C p n which is

(n times) which is obviously an unitary Hadamard matrix. The Galois field GF (p n ) is defined through the irreducible polynomial which is of Proof : The matrix elements of a given row in F are of the form

the matrix elements of the first column of the matrices R θ , θ = 0 are of the form

where we have used (3.13). But the elements (2θ) -1 when θ ∈ GF (p n )\ {0} span all θ 1 ∈ GF (p n )\ {0}. We have established that the matrix F R θ is Hadamard. This implies that all its matrix elements have modulus p -n/2 . All matrix elements of the first column of F R θ are thus of the form

with θ 1 = (2θ) -1 . Writing that its modulus is p -n/2 yields equ. (4.14).